[Coin-discuss] OsiClp* interior point stability problem

[John J Forrest]

Sebastian,

Looking at the matrices I can see that convergence could be slow.  I have a
few suggestions.

a) R0000000 sums variables == 1 so you can subtract out a constant from all
those variables and modify RHS for R0000001 and R0000002.  At present
coefficients for R0000001 seem to be 0.55 to 0.65 range - it might converge
better with a range of 0.0 to 0.1 or even scale them.
b) There are parameters you can play with for barrier method.  A quick look
didn't seem to help but I can/will send you a driver you can play with.
c) Much better I would have thought is to go back to simplex but with a
quadratic objective function added in to spread the values.
Straightforward primal quadratic seemed OK but it was quite a bit faster
with a few SLP iterations thrown in first.

So example driver (in Clp land) will follow.

John Forrest


                                                                                                                                             
  From:       "Sebastian Nowozin" <nowozin at gmail.com>                                                                                        
                                                                                                                                             
  To:         coin-discuss at list.coin-or.org                                                                                                  
                                                                                                                                             
  Date:       12/25/2007 06:11 AM                                                                                                            
                                                                                                                                             
  Subject:    [Coin-discuss] OsiClp* interior point stability problem                                                                        
                                                                                                                                             





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