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

[Sebastian Nowozin]

Hello everybody,

thanks for your numerous help.


Erling D. Andersen wrote:

> 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.

> At 12:54 04-03-2008, Sebastian Nowozin wrote:
>> 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.

I made a mistake here.  I did not try solving it using the "barr" 
command in the standalone clp solver binary.  Infact, just using "import 
toughone.mps; min; barr" works and Clp solves the problem in around 80 
minutes.  The peak memory used is ~710mb.

I only tried programmatically through the OsiClpSolverInterface class. 
I think there was a bug in my code and the interior point solver was 
never enabled: I always called OsiClpSolverInterface::resolve() because 
I expected it to behave the same as ::initialSolve() in the first 
iteration.  But it seems that ::resolve() always uses the simplex 
method, even when specifically requesting the barrier method.

The output is as follows:

Coin LP version 1.06.00, build Feb 27 2008
Clp takes input from arguments ( - switches to stdin)
Enter ? for list of commands or help
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.60848 seconds
Clp:min
Clp:barr
Dual of model has 7401 rows and 99100 columns
Coin0506I Presolve 7401 (0) rows, 99100 (0) columns and 12876400 (0) 
elements
Going dense for last 7401 rows
2.68842e+07 elements in sparse Cholesky, flop count 1.35157e+11
Clp0035I 0 Primal -160 Dual -1.08453e+09 Complementarity 1.08453e+09 - 0 
fixed, rank 7401
Clp0035I 1 Primal 9731.89 Dual -5.32553e+06 Complementarity 5.4579e+06 - 
0 fixed, rank 7401
Clp0035I 2 Primal 1558.5 Dual -26640.5 Complementarity 28822.2 - 0 
fixed, rank 7401
Clp0035I 3 Primal 22.7573 Dual -128.389 Complementarity 168.035 - 0 
fixed, rank 7401
Clp0035I 4 Primal 0.515501 Dual -1.41908 Complementarity 4.536 - 0 
fixed, rank 7401
Clp0035I 5 Primal 0.322751 Dual -0.208302 Complementarity 0.91704 - 0 
fixed, rank 7401
Clp0035I 6 Primal 0.262071 Dual -0.162953 Complementarity 0.735998 - 0 
fixed, rank 7401
Clp0035I 7 Primal 0.217889 Dual -0.136627 Complementarity 0.611273 - 0 
fixed, rank 7401
Clp0035I 8 Primal 0.146978 Dual -0.105794 Complementarity 0.441903 - 0 
fixed, rank 7401
Clp0035I 9 Primal 0.0971126 Dual -0.0870246 Complementarity 0.323115 - 0 
fixed, rank 7401
Clp0035I 10 Primal 0.0709 Dual -0.0763332 Complementarity 0.255953 - 0 
fixed, rank 7401
Clp0035I 11 Primal 0.0339217 Dual -0.0662311 Complementarity 0.179753 - 
0 fixed, rank 7401
Clp0035I 12 Primal 0.00196868 Dual -0.0582609 Complementarity 0.118438 - 
0 fixed, rank 7401
Clp0035I 13 Primal -0.0177714 Dual -0.0517536 Complementarity 0.0740791 
- 0 fixed, rank 7401
Clp0035I 14 Primal -0.028623 Dual -0.0472137 Complementarity 0.045377 - 
0 fixed, rank 7401
Clp0035I 15 Primal -0.0300834 Dual -0.0459148 Complementarity 0.0385854 
- 0 fixed, rank 7401
Clp0035I 16 Primal -0.0340665 Dual -0.0431424 Complementarity 0.0233203 
- 0 fixed, rank 7401
Clp0035I 17 Primal -0.0366924 Dual -0.041363 Complementarity 0.013562 - 
0 fixed, rank 7401
Clp0035I 18 Primal -0.0375286 Dual -0.0403955 Complementarity 0.00869336 
- 0 fixed, rank 7401
Clp0035I 19 Primal -0.0380701 Dual -0.0397789 Complementarity 0.00554524 
- 0 fixed, rank 7401
Clp0035I 20 Primal -0.0383269 Dual -0.0394453 Complementarity 0.00384998 
- 0 fixed, rank 7401
Clp0035I 21 Primal -0.0384648 Dual -0.0392227 Complementarity 0.00272949 
- 0 fixed, rank 7401
Clp0035I 22 Primal -0.0385432 Dual -0.039071 Complementarity 0.00197697 
- 0 fixed, rank 7401
Clp0035I 23 Primal -0.038576 Dual -0.0389551 Complementarity 0.0014116 - 
0 fixed, rank 7401
Clp0035I 24 Primal -0.0386061 Dual -0.0388708 Complementarity 0.00099968 
- 0 fixed, rank 7401
Clp0035I 25 Primal -0.0386268 Dual -0.0388298 Complementarity 
0.000790359 - 0 fixed, rank 7401
Clp0035I 26 Primal -0.0386388 Dual -0.0387912 Complementarity 
0.000599914 - 0 fixed, rank 7401
Clp0035I 27 Primal -0.0386499 Dual -0.0387568 Complementarity 
0.000426742 - 0 fixed, rank 7401
Clp0035I 28 Primal -0.0386579 Dual -0.0387342 Complementarity 
0.000310306 - 0 fixed, rank 7401
Clp0035I 29 Primal -0.0386632 Dual -0.0387148 Complementarity 
0.000210779 - 0 fixed, rank 7401
Clp0035I 30 Primal -0.0386646 Dual -0.0387011 Complementarity 
0.000140985 - 0 fixed, rank 7401
Clp0035I 31 Primal -0.0386662 Dual -0.0386965 Complementarity 
0.000116556 - 0 fixed, rank 7401
Clp0035I 32 Primal -0.0386672 Dual -0.038691 Complementarity 8.78759e-05 
- 0 fixed, rank 7401
Clp0035I 33 Primal -0.0386712 Dual -0.0386846 Complementarity 5.1818e-05 
- 1745 fixed, rank 7401
Clp0035I 34 Primal -0.0386728 Dual -0.0386809 Complementarity 
3.13923e-05 - 25579 fixed, rank 7401
Clp0035I 35 Primal -0.0386733 Dual -0.0386796 Complementarity 
2.40339e-05 - 39203 fixed, rank 7401
Clp0035I 36 Primal -0.0386738 Dual -0.0386782 Complementarity 1.6042e-05 
- 57071 fixed, rank 7401
Clp0035I 37 Primal -0.0386747 Dual -0.0386772 Complementarity 
1.00578e-05 - 81202 fixed, rank 7401
Clp0035I 38 Primal -0.0386749 Dual -0.0386758 Complementarity 
2.74867e-06 - 83876 fixed, rank 7401
Clp0035I 39 Primal -0.0386753 Dual -0.0386755 Complementarity 
7.89875e-07 - 92100 fixed, rank 7401
Clp0035I 40 Primal -0.0386753 Dual -0.0386754 Complementarity 
1.03922e-07 - 94470 fixed, rank 7401
Clp0035I 41 Primal -0.0386754 Dual -0.0386754 Complementarity 
1.16664e-09 - 98736 fixed, rank 7401
Clp0035I 42 Primal -0.0386754 Dual -0.0386754 Complementarity 
2.05425e-10 - 99466 fixed, rank 7401
Clp0042I Optimal
Clp0046I At end primal/dual infeasibilities 0/0, complementarity gap 0, 
objective -0.0386754
...
(now doing crossover, which I don't need).


It seems all simplex based methods fail or are extremely slow (including 
Cplex, GLPK, Clp, ...), and maybe this problem is a typical instance to 
be solved with interior point as all variables and constraints interact 
strongly.  But as John said in the other email just now, the real 
problem data might behave better.  I will let you know.

Thanks for your support,
Sebastian