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

Tue Mar 4 08:28:21 EST 2008

Hi

I tried downloading your models and solved it with the MOSEK interior-point optimizer.
The large one solved in 755sec on a reasonable fast CPU.

Erling

At 12:54 04-03-2008, Sebastian Nowozin wrote:

>Hello everybody,
>
>for a machine learning multiclass classification model we use a large 
>linear program to estimate optimal model parameters explaining given 
>training data.  The model variables are highly coupled in the sense that 
>for most variables there exist a constraint coupling any pair of variables.
>
>As we do not have the training data yet, I generated models with random 
>data for testing my code and the solver.  The actual data might behave 
>much better due to redundancy and simplicity, however we plan to solve 
>problems roughly ten times the size of the problem below (so the final 
>nnz would be approximately 100 million).  I generate the model directly 
>in a .cpp file, but write a MPS file for debugging purposes.
>
>However, it seems COIN Clp 1.6.0 shipped with Osi 0.97.1 is unable to 
>solve the problem.
>
>I put two .mps.bz2 files of structurally identical problems here:
>   http://user.cs.tu-berlin.de/~nowozin/mps/
>The "easyone.mps" is small and all solvers I tried solve it without 
>problems.  The "toughone.mps" is quite large (99100 rows, 7401 columns, 
>~12.9 million nnz, you need 1GB free RAM to load/solve the model).
>
>The output of Clp looks like this, where the number of infeasibilities 
>does not seem to decrease.
>
>Clp:import toughone.mps
>At line 1 NAME          BLANK
>At line 2 ROWS
>At line 99104 COLUMNS
>At line 6541006 RHS
>At line 6541057 BOUNDS
>At line 6541059 ENDATA
>Problem BLANK has 99100 rows, 7401 columns and 12876400 elements
>Model was imported from ./toughone.mps in 7.65248 seconds
>Clp:solve
>Dual of model has 7401 rows and 99100 columns
>Coin0506I Presolve 7401 (0) rows, 99100 (0) columns and 12876400 (0) 
>elements
>Clp0014I Perturbing problem by 0.001 % of 0.73339 - largest nonzero 
>change 3.02687e-05 (% 0.0846218) - largest zero change 9.99969e-05
>Clp0006I 0  Obj -482.729 Primal inf 2.39382e+06 (6401)
>Clp0006I 223  Obj -482.592 Primal inf 1.54823e+07 (4660)
>Clp0006I 446  Obj -482.52 Primal inf 6.22071e+07 (4180)
>Clp0006I 669  Obj -482.488 Primal inf 3.04425e+08 (3923)
>Clp0006I 892  Obj -482.471 Primal inf 6.82636e+07 (4045)
>Clp0006I 1115  Obj -482.458 Primal inf 1.77363e+08 (4052)
>Clp0006I 1338  Obj -482.443 Primal inf 1.39113e+08 (4286)
>Clp0006I 1561  Obj -482.43 Primal inf 2.07872e+08 (4257)
>Clp0006I 1784  Obj -482.419 Primal inf 6.22298e+07 (4334)
>Clp0006I 2007  Obj -482.405 Primal inf 1.17816e+08 (4379)
>Clp0006I 2230  Obj -482.393 Primal inf 2.05141e+08 (4363)
>Clp0006I 2453  Obj -482.381 Primal inf 7.36075e+07 (4400)
>Clp0006I 2676  Obj -482.368 Primal inf 7.92307e+07 (4414)
>Clp0006I 2899  Obj -482.356 Primal inf 1.06462e+08 (4462)
>Clp0006I 3122  Obj -482.343 Primal inf 1.53225e+08 (4488)
>Clp0006I 3345  Obj -482.33 Primal inf 1.09378e+08 (4496)
>Clp0006I 3568  Obj -482.319 Primal inf 1.42576e+08 (4505)
>Clp0006I 3791  Obj -482.308 Primal inf 4.68459e+08 (4677)
>Clp0006I 4014  Obj -482.298 Primal inf 1.60121e+08 (4581)
>Clp0006I 4237  Obj -482.289 Primal inf 4.27189e+07 (4629)
>Clp0006I 4460  Obj -482.277 Primal inf 6.13483e+07 (4631)
>Clp0006I 4683  Obj -482.267 Primal inf 5.522e+07 (4790)
>Clp0006I 4906  Obj -482.254 Primal inf 4.94801e+07 (4755)
>Clp0006I 5086  Obj -482.244 Primal inf 4.86999e+08 (4802)
>Clp0006I 5269  Obj -482.236 Primal inf 1.8662e+09 (4747)
>Clp0006I 5352  Obj -482.23 Primal inf 3.93626e+07 (4805)
>Clp0006I 5575  Obj -482.217 Primal inf 6.28133e+07 (4862)
>Clp0006I 5798  Obj -482.205 Primal inf 4.68871e+07 (4840)
>Clp0006I 6021  Obj -482.192 Primal inf 3.12843e+08 (4807)
>Clp0006I 6133  Obj -482.184 Primal inf 4.45966e+07 (4830)
>Clp0006I 6356  Obj -482.172 Primal inf 5.81011e+07 (4898)
>Clp0006I 6579  Obj -482.161 Primal inf 6.83596e+07 (4901)
>Clp0006I 6693  Obj -482.156 Primal inf 3.40449e+08 (4926)
>Clp0006I 6916  Obj -482.143 Primal inf 7.19014e+07 (4930)
>Clp0006I 7135  Obj -482.129 Primal inf 1.2956e+08 (4975)
>Clp0006I 7358  Obj -482.118 Primal inf 1.05719e+08 (5062)
>Clp0006I 7581  Obj -482.106 Primal inf 7.27903e+07 (4956)
>...
>
>I tried the primal simplex, dual simplex and barrier methods with very 
>similar behaviour.  Due to the large values, it seems there may be a 
>scaling problem.  One nice thing I noted though is the low memory usage 
>of Clp.
>
>GLPK 4.16 nibbled away the whole night on the problem, consistently 
>decreasing the number of infeasibilities (I assume it would have solved 
>the problem eventually, but I aborted after 95,000 iterations and around 
>10 hours of computation time).
>
>I also tried Ilog Cplex 9.1.0, which seems to make consistent progress 
>in solving the problem, but now is at ~15,000 seconds and iteration 
>143,500 and still runs.  I will save the optimal solution once obtained, 
>if you are interested.
>
>
>I know the above problem is difficult, but it would be great if we could 
>use Clp to solve it.  Do you have advice on pivoting rules, scaling and 
>perturbations I should try?  I am willing to give up some accuracy for 
>fast approximate solutions, as variations of the problem will be solved 
>many times (for model selection and estimating generalization 
>performance of the resulting classifier).  Also, the achieved objective 
>is more important than the variable values, as the objective has a 
>direct geometric interpretation.
>
>Would it help if I provide a good initial basic solution? (As I do not 
>know how to generate a basis for it I would just add constraints fixing 
>all variables, solve, then remove the constraints and resolve.  Does 
>this make sense or is there a better way?)
>
>Thanks,
>Sebastian
>_______________________________________________
>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 
************************************************************************* 