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

[Erling D. Andersen]

Hi

The crossover may come handy if you want to solve some closely related
problems because then you can hotstart the simplex optimizers.

Just out of curiosity. Does Clp crossover these days. Or do we commercial guys 
still have an edge there.

Erling

At 16:28 07-03-2008, Sebastian Nowozin wrote:

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

*************************************************************************
MOSEK ApS     
C/O Symbion Science Park    
Fruebjergvej 3, Boks 16
DK-2100 Copenhagen O
Denmark

Phone (work): +45 3917 9907
Mobile-phone: +45 2362 9520
Fax:               +45 3917 9823
Email: e.d.andersen at mosek.com
Homepage: http://erling.andersen.name 
*************************************************************************