[Coin-discuss] OsiClp* interior point stability problem

[Laszlo Ladanyi]

Hi Sebastian,

I don't know how stable the Clp interior solver is (John Forrest is the man to 
answer that question), but you might want to try to use the Volume Algorithm. 
It does have an OSI interface (OsiVol). It gets near the center of the optimal 
face (within 2-5%) much faster than any interior point solver, and that 
accuracy is usually enough to do column generation. And when convergence 
starts to slow down you can switch to Clp's simplex solver.

HHope this helps,
--Laci

On Tue, 25 Dec 2007, Sebastian Nowozin wrote:

> 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
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>