source: trunk/README.md @ 2423

Last change on this file since 2423 was 2423, checked in by stefan, 3 months ago

update link to users guide

  • Property svn:eol-style set to native
File size: 5.8 KB
Line 
1# CLP
2
3Clp (*C*oin-or *l*inear *p*rogramming) is an open-source linear programming solver.
4It is primarily meant to be used as a callable library, but a basic, stand-alone executable version is also available.
5It is designed to find solutions of mathematical optimization problems of the form
6
7minimize   c'x
8such that  lhs ≤ Ax ≤ rhs
9and        lb ≤ x ≤ ub
10
11
12CLP includes primal and dual Simplex solvers.
13Both 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).
14The dual algorithm has Dantzig and Steepest edge row pivot choices; new ones may be provided by the user.
15The same is true for the column pivot choice of the primal algorithm.
16The primal can also use a non linear cost which should work for piecewise linear convex functions.
17CLP also includes a barrier method for solving LPs.
18
19
20Clp 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).
21It is available from the [COIN-OR initiative](http://www.coin-or.org/).
22The code is written primarily by John J. Forrest, now retired from IBM Research.
23The project is currently managed by John Forrest, Lou Hafer, [Julian Hall](https://www.maths.ed.ac.uk/hall/), and Matthew Saltzman.
24
25The Clp website is https://github.com/coin-or/Clp.
26
27Clp 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
32To build Clp from source, obtain the `coinbrew` script from
33https://coin-or.github.io/coinbrew/
34and 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
42The `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
57If you have `Doxygen` available, you can build a HTML documentation by typing
58
59 `make doxydoc`
60
61in the build directory.
62If Clp was build via `coinbrew`, then the build directory is `./build/Clp`.
63The doxygen documentation main file is found at `./doxydoc/html/index.html` in the build directory.
64
65If `Doxygen` is not available, you can use also use [this link](http://www.coin-or.org/Doxygen/Clp).
66
67## Project Links
68
69Support:
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 
74Documentation:
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
79Interfaces:
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
90The CLP barrier method solves convex QPs as well as LPs.
91In general, a barrier method requires implementation of the algorithm, as well as a fast Cholesky factorization.
92CLP provides the algorithm, and is expected to have a reasonable factorization implementation.
93However, 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
97The Cholesky interface is flexible enough so that a variety of Cholesky ordering and factorization codes can be used.
98Interfaces 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?
107The best outcome would be to have an existing ordering code available as part of the COIN-OR distribution under the EPL.
108However, 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?
112The 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".
113However, 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?
117The interior point algorithm for quadratic programming is much more elegant and normally much faster than the quadratic simplex code.
118Caution is suggested with the presolve as not all bugs have been found and squashed when a quadratic objective is used.
119One may wish to switch off the crossover to a basic feasible solution as the simplex code can be slow.
120The 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.
Note: See TracBrowser for help on using the repository browser.