[Coin-discuss] Clp 1.6.0 fails to make visible progress on a large model

[Sebastian Nowozin]

Hello John and the others who have helped,

I now have a good way to solve these problems quickly for my 
application, using OsiMsk* and the Mosek interior point solver (who 
kindly provided a student license).

Also, the random problem I posted earlier behaves very similar using 
real problem data.  I put up a benchmark file of a typical real world 
problem here:

   http://user.cs.tu-berlin.de/~nowozin/mps/class1.mps.bz2

It is smaller than the previous one (using only 400MB memory and the Clp 
barrier method can solve it in 20 minutes, the simplex method in two 
hours.  The optimal solution is -0.0737078.

This problem might be interesting because it clearly makes all simplex 
methods go very slowly (I tested Clp, GLPK and Cplex), whereas all 
barrier codes I tried (Clp, Cplex, Mosek) can solve the problem.  Cplex 
and Mosek are roughly equally fast with Mosek having a slight edge (and 
it can do a crossover -- which I don't need -- in around 15 minutes). 
Clp's barrier solver takes around 10 times as much time but is still 
faster than any simplex method I tried.  To summarize, a) for this 
problem class its necessary to use the interior-point codes, and b) as 
John said, there is a gap between Clp's barrier solver and the 
commercial ones.

Thanks for all your help,
Sebastian

John J Forrest wrote:

 > [...]
> Clp probably has one of the worlds worst interior point codes, but using a
> dense Cholesky and doing no crossover it solved in about 90 minutes on my
> Thinkpad (Okay - I need to modify code as I could see a small bug when it
> stopped with the exact parameters I used).
> 
> I had to shut my laptop down but it looked as if I could get it to solve
> using simplex in 6-10 hours.  If your randomness is in element values but
> not in structure then a real problem of that size would be faster but a
> larger problem would have great difficulties as the factorization looks as
> if it gets dense.  If your randomness was in structure then you may have
> some hope for a genuine larger problem.
> 
> John Forrest