[Coin-discuss] OsiClp* interior point stability problem

[Sebastian Nowozin]

Hello everybody,

I am using COIN Clp over the OsiClp interface in order to solve a
large scale linear program by means of column generation.  The linear
programming problem comes from a machine learning method known as
LPBoost (http://en.wikipedia.org/wiki/LPBoost).  In the solution
process it is advantageous to balance subsets of variables which
behave equally, which corresponds directly to choosing a central point
in the solution vertex of the resulting LP  (we know that such
solutions will have a better practical effect on the generalization
performance of the LPBoost classifier).  Hence the use of an interior
point method will be advantageous.  The simplex method has the
advantage of rapid warmstarts for the column generation scheme, but in
this particular application the convergence of the overall scheme will
be much quicker if a central point in the intermediate solution
vertices is choosen.

For small scale problems (a few thousand rows) the Clp interior point
method works great.  However, if the problem dimensions are enlarged,
to some 10e5 rows, the method fails.

I put three MPS files produced after a solver-failure online at this address:
http://user.cs.tu-berlin.de/~nowozin/clp/

All fail when the interior point method is used (with both presolve
on/off tried), but work fine with the simplex method.  For the reasons
outlined above I would like to know if all interior point methods in
general have problems with this extremely degenerate linear programs,
or if this is maybe just a problem with the COIN Clp solver.

Please let me know of your experiences with the COIN Clp interior
point code and any fixes/workarounds I could apply.

Thanks and happy holidays,
Sebastian