1 | # CLP |
---|
2 | |
---|
3 | Clp (*C*oin-or *l*inear *p*rogramming) is an open-source linear programming solver. |
---|
4 | It is primarily meant to be used as a callable library, but a basic, stand-alone executable version is also available. |
---|
5 | It is designed to find solutions of mathematical optimization problems of the form |
---|
6 | |
---|
7 | minimize c'x |
---|
8 | such that lhs ≤ Ax ≤ rhs |
---|
9 | and lb ≤ x ≤ ub |
---|
10 | |
---|
11 | |
---|
12 | CLP includes primal and dual Simplex solvers. |
---|
13 | Both dual and primal algorithms can use matrix storage methods provided by the user (0-1 and network matrices are already supported in addition to the default sparse matrix). |
---|
14 | The dual algorithm has Dantzig and Steepest edge row pivot choices; new ones may be provided by the user. |
---|
15 | The same is true for the column pivot choice of the primal algorithm. |
---|
16 | The primal can also use a non linear cost which should work for piecewise linear convex functions. |
---|
17 | CLP also includes a barrier method for solving LPs. |
---|
18 | |
---|
19 | |
---|
20 | Clp is written in C++ and is released as open source code under the [Eclipse Public License (EPL)](http://www.opensource.org/licenses/eclipse-1.0). |
---|
21 | It is available from the [COIN-OR initiative](http://www.coin-or.org/). |
---|
22 | The code is written primarily by John J. Forrest, now retired from IBM Research. |
---|
23 | The project is currently managed by John Forrest, Lou Hafer, [Julian Hall](https://www.maths.ed.ac.uk/hall/), and Matthew Saltzman. |
---|
24 | |
---|
25 | The Clp website is https://github.com/coin-or/Clp. |
---|
26 | |
---|
27 | Clp is available in [Debian](http://packages.debian.org/search?searchon=sourcenames&keywords=clp) and [Ubuntu](https://launchpad.net/ubuntu/+source/clp). |
---|
28 | |
---|
29 | |
---|
30 | ## Getting Started using CoinBrew |
---|
31 | |
---|
32 | To build Clp from source, obtain the `coinbrew` script from |
---|
33 | https://coin-or.github.io/coinbrew/ |
---|
34 | and run |
---|
35 | |
---|
36 | |
---|
37 | /path/to/coinbrew fetch --mainProj=Clp |
---|
38 | /path/to/coinbrew build --mainProj=Clp --test |
---|
39 | /path/to/coinbrew install --mainProj=Clp |
---|
40 | |
---|
41 | |
---|
42 | The `coinbrew` script will fetch [these](Dependencies) additional projects. |
---|
43 | |
---|
44 | |
---|
45 | ## Getting Started without CoinBrew (Expert users) |
---|
46 | |
---|
47 | 0. Install [these Dependencies](Dependencies) |
---|
48 | 1. Obtain the source code, e.g., from https://github.com/coin-or/Clp |
---|
49 | 2. Run `./configure -C` to generate makefiles |
---|
50 | 3. Run `make` to build the CoinUtils library |
---|
51 | 4. Run `make test` to build and run the CoinUtils unit test program |
---|
52 | 5. Run `make install` to install library and header files. |
---|
53 | |
---|
54 | |
---|
55 | ## Doxygen Documentation |
---|
56 | |
---|
57 | If you have `Doxygen` available, you can build a HTML documentation by typing |
---|
58 | |
---|
59 | `make doxydoc` |
---|
60 | |
---|
61 | in the build directory. |
---|
62 | If Clp was build via `coinbrew`, then the build directory is `./build/Clp`. |
---|
63 | The doxygen documentation main file is found at `./doxydoc/html/index.html` in the build directory. |
---|
64 | |
---|
65 | If `Doxygen` is not available, you can use also use [this link](http://www.coin-or.org/Doxygen/Clp). |
---|
66 | |
---|
67 | ## Project Links |
---|
68 | |
---|
69 | Support: |
---|
70 | * [COIN-OR Initiative](http://www.coin-or.org/) |
---|
71 | * [mailing list](http://list.coin-or.org/mailman/listinfo/clp) |
---|
72 | * [Report a bug](https://github.com/coin-or/Clp/issues/new) |
---|
73 | |
---|
74 | Documentation: |
---|
75 | * [Doxygen-generated html documentation](http://www.coin-or.org/Doxygen/Clp) |
---|
76 | * Source code [examples](Clp/examples) |
---|
77 | * [User's Guide](https://coin-or.github.io/Clp) (from 2004) |
---|
78 | |
---|
79 | Interfaces: |
---|
80 | * [Matlab Interface + Windows x86 & x64 Interface Binaries (OPTI Toolbox)](https://www.inverseproblem.co.nz/OPTI/) |
---|
81 | * [Julia interface](https://github.com/JuliaOpt/Clp.jl) |
---|
82 | * [R and CLP - a quick start](https://cran.r-project.org/web/packages/clpAPI/vignettes/clpAPI.pdf) |
---|
83 | * [Java and CLP - performs well](http://orinanobworld.blogspot.co.uk/2016/06/using-clp-with-java.html) |
---|
84 | |
---|
85 | |
---|
86 | ## FAQ (from 2004) |
---|
87 | |
---|
88 | ### The barrier method sounds interesting, what are some of the details? |
---|
89 | |
---|
90 | The CLP barrier method solves convex QPs as well as LPs. |
---|
91 | In general, a barrier method requires implementation of the algorithm, as well as a fast Cholesky factorization. |
---|
92 | CLP provides the algorithm, and is expected to have a reasonable factorization implementation. |
---|
93 | However, the sparse factorization requires a good ordering algorithm, which the user is expected to provide (perhaps a better factorization code as well). |
---|
94 | |
---|
95 | ### Which Cholesky factorizations codes are supported by CLP's barrier method? |
---|
96 | |
---|
97 | The Cholesky interface is flexible enough so that a variety of Cholesky ordering and factorization codes can be used. |
---|
98 | Interfaces are provided to each of the following: |
---|
99 | * Anshul Gupta's WSSMP parallel enabled ordering and factorization code |
---|
100 | * Sivan Toledo's TAUCS parallel enabled factorization code (the package includes third party ordering codes) |
---|
101 | * University of Florida's Approximate Minimum Degree (AMD) ordering code (the CLP native factorization code is used with this ordering code) |
---|
102 | * CLP native code: very weak ordering but competitive nonparallel factorization |
---|
103 | * Fast dense factorization |
---|
104 | |
---|
105 | |
---|
106 | ### When will CLP have a good native ordering? |
---|
107 | The best outcome would be to have an existing ordering code available as part of the COIN-OR distribution under the EPL. |
---|
108 | However, if this is not possible, the native ordering will be made respectable. |
---|
109 | |
---|
110 | |
---|
111 | ### Is the barrier code as mature as the simplex code? |
---|
112 | The simplex code has been exposed to user testing for a while and the principal author, John Forrest, knows more about simplex algorithms than interior point algorithms, so the answer is "no". |
---|
113 | However, it performs well on test sets and seems to be more reliable than some commercially available codes (including OSL). |
---|
114 | |
---|
115 | |
---|
116 | ### Which algorithm should I use for quadratic programming and should I keep an eye open for any issues? |
---|
117 | The interior point algorithm for quadratic programming is much more elegant and normally much faster than the quadratic simplex code. |
---|
118 | Caution is suggested with the presolve as not all bugs have been found and squashed when a quadratic objective is used. |
---|
119 | One may wish to switch off the crossover to a basic feasible solution as the simplex code can be slow. |
---|
120 | The sequential linear code is useful as a "crash" to the simplex code; its convergence is poor but, say, 100 iterations could set up the problem well for the simplex code. |
---|