IMPORTANT
This project is now really advanced and close to a stable release.
You can find more informations at: https://github.com/ycollet/scilab-mip
Description
Integrate a new module to perform adavance linear programming optimization:
- Use sparse matrixes to define the optimization problem;
- Deal with integer and binary variables;
- Use efficient optimization procedures (like branch and bound, Gomory cuts, etc ...).
Ideas
Several libraries exist. From these libraries, three main libraries can be highlighted:
- GLPK: a free linear programming library. It deals with sparse matrixes, allows integer and binary variables. The only problem as far as I can see: when some problem are meet by GLPK (access to an index out of bounds), GLPK call 'abort' and, when scilab is interfaced to GLPK, this call makes scilab hangs. Seems quite efficient and still developped by a community;
- LPSOLVE: a free linear programming library. It can deal with sparse matrixes, but you need to enter these matrixes column by column. Seems quite efficient and still developped by a community;
- COIN-OR: The Coin-Or project has for aim to developped tools for linear and quadratic programming for research. They have developped a library of classes which allows to perform linear programming, quadratic programming, MIP, etc ... This library is certainly the most efficient of all these three library (it compares favourably to CPLEX). It gives access to branch and bound, several kind of cuts for integer programming, classic simplex, etc ... Seems quite efficient and still developped by a community;
Work done
A new interface to GLPK has been developped (it doesn't rely anymore on a mex interface).
A new interface to CLP, CBC, IPOPT, BONMIN, CSDP, OBOE has been developped.
Interfaces to read MPS, LP and SDPA files have been developped.
A new interface to LPSOLVE has been developped (it doesn' rely on a mex interface anymore).
Up to now, the scilab-mip is available on request (send a mail to ycollet et freesurf dot fr) because some parts are lacking:
- the documentation;
- the installation process.
All the sources are hosted at https://github.com/ycollet/scilab-mip
Work to be done
What must be done in this CoinOR project:
An interface to OSI. The Open Solver Interface allows to use several solvers (commercial and open source) through a common interface. The goal should be to write an interface to scilab which allows to switch dynamically between solvers (CPLEX, GLPK, LPSOLVE, CLP for examples).
An interface to DyLP. A tool to solve linear programming problems via dynamic simplex.
An interface to Vol. A tool which usesVolume Algorithm, a subgradient algorithm that also computes approximate primal solutions.
An interface to SMI. Smi is an open-source interface for modeling stochastic linear programming problems.
An interface to DFO. Derivative-Free Optimization, a package for solving general nonlinear optimization problems when derivatives are unavailable.
An interface to OptiML. OptiML stands for Optimization methods in Machine Learning.
You can have a look at the CLP interface and the IPOPT interface on https://github.com/ycollet/scilab-mip.
Links
Benchmarks of LP Codes
These benchmarks can be found on http://plato.asu.edu/bench.html.