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

Wed Mar 5 04:10:44 EST 2008

Sebastian,

The bit of the log file you show looks correct.  With simplex there is no
guarantee infeasibilities will be monotonically decreasing.  The objective
is increasing which is correct.

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

  From:       Sebastian Nowozin <nowozin at gmail.com>                                                                 

  To:         Discussions about open source software for Operations Research <coin-discuss at list.coin-or.org>        

  Date:       03/04/2008 07:01 AM                                                                                   

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

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