Q: What is CLP?
A: (DN 08/27/04) The COIN-OR LP code is designed to be a high quality Simplex code provided under the terms of the Eclipse Public License. CLP is written in C++, and is primarily intended to be used as a callable library (though a rudimentary stand-alone executable exists). The first release was version .90. The current release is version 1.00.2.
Q: What are some of the features of CLP?
A: (DN 08/27/04) CLP includes primal and dual Simplex solvers. 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). The dual algorithm has Dantzig and Steepest edge row pivot choices; new ones may be provided by the user. The same is true for the column pivot choice of the primal algorithm. The primal can also use a non linear cost which should work for piecewise linear convex functions. CLP also includes a barrier method for solving LPs.
Q: How do I obtain and install CLP?
A: (DN 08/27/04) Please see the COIN-OR FAQ for details on how to obtain and install COIN-OR modules.
Q: Is CLP reliable?
A: (DN 09/07/04) CLP has been tested on many problems of up to 1.5 million constraints and has shown itself as reliable as OSL. It is also being tested in the context of developing CBC (“Coin Branch and Cut”, which is used to solve integer programs); it is now considered reliable enough to be at version 1.0.
Q: On which platforms does CLP run?
A: (DN 08/27/04) CLP compiles and has been tested (to varying degrees) on the following platforms:
Linux using g++ version 3.1.1 (or later)
Windows using Microsoft Visual C++ 6
Windows using cygwin
AIX using xIC (not supported in the current Makefile)
Q: Is there any documentation for CLP?
A: (DN 09/16/04) An early release of a User Guide is available on the CLP user’s guide page. Also available is a list of CLP class descriptions generated by Doxygen.
Q: Is CLP as fast as OSL?
A: (DN 08/27/04) CLP uses sparse matrix techniques designed for very large problems. The design criteria were for it not to be too slow. Some speed has been sacrificed to make the code less opaque OSL (not difficult!).
Q: When will version 1.0 of CLP be available?
A: (DN 08/27/04) Version 1.0 was released in time for the 2004 INFORMS Annual Meeting (24-27 October, 2004).
Q: The barrier method sounds interesting, what are some of the details?
A: (DN 08/30/04) The CLP barrier method solves convex QPs as well as LPs. In general, a barrier method requires implementation of the algorithm, as well as a fast Cholesky factorization. CLP provides the algorithm, and is expected to have a reasonable factorization implementation by the release of CLP version 1.0. However, the sparse factorization requires a good ordering algorithm, which the user is expected to provide (perhaps a better factorization code as well).
Q: Which Cholesky factorizations codes are supported by CLP’s barrier method?
A: (DN 09/16/04) The Cholesky interface is flexible enough so that a variety of Cholesky ordering and factorization codes can be used. Interfaces are provided to each of the following:
Anshul Gupta’s WSSMP parallel enabled ordering and factorization code
Sivan Toledo’s TAUCS parallel enabled factorization code (the package includes third party ordering codes)
University of Florida’s Approximate Minimum Degree (AMD) ordering code (the CLP native factorization code is used with this ordering code)
CLP native code: very weak ordering but competitive nonparallel factorization
Fast dense factorization
Q: When will CLP have a good native ordering?
A: (DN 09/16/04) The best outcome would be to have an existing ordering code available as part of the COIN distribution under the EPL. However, if this is not possible, the native ordering will be made respectable.
Q: Is the barrier code as mature as the simplex code?
A: (DN 09/16/04) The simplex code has been exposed to user testing for more than a year and and the principal author, John Forrest, knows more about simplex algorithms than interior point algorithms, so the answer is “no”. However, it performs well on test sets and seems to be more reliable than some commercially available codes (including OSL).
Q: Which algorithm should I use for quadratic programming and should I keep an eye open for any issues?
A: (DN 09/16/04) The interior point algorithm for quadratic programming is much more elegant and normally much faster than the quadratic simplex code. Caution is suggested with the presolve as not all bugs have been found and squashed when a quadratic objective is used. One may wish to switch off the crossover to a basic feasible solution as the simplex code can be slow. 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.
Q: What can the community do to help?
A: (DN 09/09/04) A lot! A good first step would be to join the CLP mailing lists. Some other possibilities:
Comment on the design
Break the code, or better yet, mend it.
Add non-English language support in your own favo(u)rite language.
Improve the CLP executable. In particular it would be nice to be
able to link the executable’s online help system with the existing
CLP Samples (e.g. entering presol??? would give the user
references to all CLP Sample files which use presolve).
Implement a dual Simplex method for QPs (quadratic programs)
Implement a parametric Simplex method
Implement a true network Simplex method (network matrix and factorization are already in place, but the method is not)
Fill the holes in the barrier method mentioned above.