[Symphony-tickets] [SYMPHONY] #122: SYMPHONY unable to solve a problem that can be solved by COIN CLP/CBC and other solvers. Results with all these attached. SYMPHONY solves the LP relaxation and then quits with no additional information.
SYMPHONY
coin-trac at coin-or.org
Fri Sep 13 09:17:51 EDT 2013
#122: SYMPHONY unable to solve a problem that can be solved by COIN CLP/CBC and
other solvers. Results with all these attached. SYMPHONY solves the LP
relaxation and then quits with no additional information.
-----------------------+-------------------
Reporter: GIrisarri | Owner: tkr
Type: defect | Status: new
Priority: normal | Milestone:
Component: Not Sure | Version: 5.5.1
Keywords: |
-----------------------+-------------------
SYMPHONY:
CONSTRAINTS: 16115
VARS: 18292
NONZEROS: 72491 (72491)
Starting Preprocessing...
Preprocessing finished...
coefficients modified: 2068
bounds improved: 4920
constraints removed: 6119
variables fixed: 5855
Problem has
9996 constraints
12437 variables
55671 nonzero coefficients
Total Presolve Time: 1.000000...
Solving...
granularity set at 0.000000
****************************************************
* Now processing NODE 0 LEVEL 0 (from TM)
****************************************************
solving root lp relaxation
The LP value is: 698939.261 [0,1687]
c-length - max_row - max-col - dens: 100 - 26 - 181 - 0.00044
real 0m1.836s
user 0m0.000s
sys 0m0.000s
COINOR: CLP, CBC
CONSTRAINTS: 16115
VARS: 18292
NONZEROS: 69897
Cbc0045I Heuristic Unknown took 0 seconds (no good)
Cbc0045I Heuristic Unknown took 0 seconds (no good)
Cbc0046I Root node pass 1, 16115 rows, 0 total tight cuts - objective
698939.26
Cbc0046I Root node pass 2, 16142 rows, 27 total tight cuts - objective
700522.24
Cbc0046I Root node pass 3, 16146 rows, 31 total tight cuts - objective
701165.72
Cbc0046I Root node pass 4, 16149 rows, 34 total tight cuts - objective
701840.62
Cbc0046I Root node pass 5, 16151 rows, 36 total tight cuts - objective
702011.92
Cbc0046I Root node pass 6, 16153 rows, 38 total tight cuts - objective
702198.67
Cbc0046I Root node pass 7, 16154 rows, 39 total tight cuts - objective
702304.36
Cbc0046I Root node pass 8, 16152 rows, 37 total tight cuts - objective
702322.17
Cbc0046I Root node pass 9, 16156 rows, 41 total tight cuts - objective
702339.25
Cbc0046I Root node pass 10, 16156 rows, 41 total tight cuts - objective
702355.38
Cbc0046I Root node pass 11, 16154 rows, 39 total tight cuts - objective
702377.29
Cbc0046I Root node pass 12, 16157 rows, 42 total tight cuts - objective
702382.84
Cbc0046I Root node pass 13, 16158 rows, 43 total tight cuts - objective
702389.96
Cbc0046I Root node pass 14, 16163 rows, 48 total tight cuts - objective
702392.16
Cbc0046I Root node pass 15, 16162 rows, 47 total tight cuts - objective
702395.99
Cbc0046I Root node pass 16, 16159 rows, 44 total tight cuts - objective
702399.54
Cbc0046I Root node pass 17, 16163 rows, 48 total tight cuts - objective
702400.69
Cbc0046I Root node pass 18, 16167 rows, 52 total tight cuts - objective
702402.9
Cbc0046I Root node pass 19, 16167 rows, 52 total tight cuts - objective
702405.14
Cbc0046I Root node pass 20, 16164 rows, 49 total tight cuts - objective
702409.14
Cbc0031I 48 added rows had average density of 478.22917
Cbc0013I At root node, 48 cuts changed objective from 698939.26 to
702411.45 in 20 passes
Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 1
column cuts (1 active)
Cbc0014I Cut generator 1 (Gomory) - 326 row cuts average 798.2 elements, 0
column cuts (48 active)
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0
column cuts (0 active)
Cbc0014I Cut generator 3 (OddHole) - 0 row cuts average 0.0 elements, 0
column cuts (0 active)
Cbc0014I Cut generator 4 (Clique) - 0 row cuts average 0.0 elements, 0
column cuts (0 active)
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0
column cuts (0 active)
Cbc0014I Cut generator 6 (MixedIntegerRounding) - 0 row cuts average 0.0
elements, 0 column cuts (0 active)
Cbc0010I After 0 nodes, 1 on tree, 1e+050 best solution, best possible
702411.45 (5.54 seconds)
Cbc0015I Node 1 Obj 702415.15 Unsat 43 depth 1
Cbc0015I Node 2 Obj 705355.15 Unsat 27 depth 1
Cbc0015I Node 3 Obj 702415.15 Unsat 42 depth 2
Cbc0015I Node 4 Obj 702556.66 Unsat 11 depth 3
Cbc0015I Node 5 Obj 707959.54 Unsat 28 depth 2
Cbc0015I Node 6 Obj 708261.13 Unsat 21 depth 3
Cbc0015I Node 7 Obj 702558.3 Unsat 9 depth 4
Cbc0015I Node 8 Obj 2302243.2 Unsat 14 depth 4
Cbc0015I Node 9 Obj 702567.06 Unsat 6 depth 5
Cbc0015I Node 10 Obj 1301625.6 Unsat 5 depth 5
Cbc0015I Node 11 Obj 702567.06 Unsat 4 depth 6
Cbc0015I Node 12 Obj 1701817.7 Unsat 11 depth 6
Cbc0015I Node 13 Obj 702567.06 Unsat 3 depth 7
Cbc0015I Node 14 Obj 702567.06 Unsat 2 depth 8
Cbc0012I Integer solution of 702567.06 found by Unknown after 4246
iterations and 14 nodes (10.32 seconds)
Cbc0001I Search completed - best objective 702567.0604600008, took 4308
iterations and 16 nodes (10.36 seconds)
Cbc0032I Strong branching done 242 times (9027 iterations), fathomed 0
nodes and fixed 0 variables
Cbc0035I Maximum depth 8, 0 variables fixed on reduced cost
Branch and cut took 10.574 seconds, 16 nodes with objective 702567
Finished
real 0m11.508s
user 0m0.000s
sys 0m0.015s
COINMP:
Welcome to the CBC MILP Solver
Version: 2.7
Build Date: Nov 2 2011
command line - CoinMP -solve -quit (default strategy 1)
Continuous objective value is 698939 - 0.14 seconds
Cgl0002I 96 variables fixed
Cgl0003I 24 fixed, 0 tightened bounds, 441 strengthened rows, 0
substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 86 strengthened rows, 0
substitutions
Cgl0004I processed model has 7700 rows, 9620 columns (528 integer) and
51185 elements
Cbc0038I Pass 1: (0.96 seconds) suminf. 0.00000 (0) obj. 1.45973e+007
iterations 710
Cbc0038I Solution found of 1.45973e+007
Cbc0038I Before mini branch and bound, 506 integers at bound fixed and
8151 continuous
Cbc0038I Full problem 7700 rows 9620 columns, reduced to 107 rows 227
columns
Cbc0038I Mini branch and bound improved solution from 1.45973e+007 to
7.59676e+006 (1.05 seconds)
Cbc0038I Freeing continuous variables gives a solution of 7.59676e+006
Cbc0038I Round again with cutoff of 6.90698e+006
Cbc0038I Pass 2: (1.17 seconds) suminf. 0.06163 (5) obj. 6.90698e+006
iterations 271
Cbc0038I Pass 3: (1.20 seconds) suminf. 0.00000 (0) obj. 6.90698e+006
iterations 161
Cbc0038I Solution found of 6.90698e+006
Cbc0038I Before mini branch and bound, 506 integers at bound fixed and
8088 continuous
Cbc0038I Full problem 7700 rows 9620 columns, reduced to 181 rows 321
columns
Cbc0038I Mini branch and bound improved solution from 6.90698e+006 to
703420 (1.28 seconds)
Cbc0038I Freeing continuous variables gives a solution of 703170
Cbc0038I Round again with cutoff of 702324
Cbc0038I Reduced cost fixing fixed 153 variables on major pass 3
Cbc0038I Pass 4: (1.38 seconds) suminf. 0.71041 (7) obj. 702324
iterations 185
Cbc0038I Pass 5: (1.51 seconds) suminf. 1.06373 (3) obj. 702324
iterations 1017
Cbc0038I Pass 6: (1.61 seconds) suminf. 0.39157 (3) obj. 702324
iterations 792
Cbc0038I Pass 7: (1.81 seconds) suminf. 2.26568 (13) obj. 702324
iterations 1047
Cbc0038I Pass 8: (1.91 seconds) suminf. 1.27404 (10) obj. 702324
iterations 569
Cbc0038I Pass 9: (2.07 seconds) suminf. 2.44627 (9) obj. 702324
iterations 791
Cbc0038I Pass 10: (2.16 seconds) suminf. 0.71046 (7) obj. 702324
iterations 583
Cbc0038I Pass 11: (2.29 seconds) suminf. 1.16122 (3) obj. 702324
iterations 792
Cbc0038I Pass 12: (2.44 seconds) suminf. 0.39158 (3) obj. 702324
iterations 1139
Cbc0038I Pass 13: (2.57 seconds) suminf. 1.53518 (8) obj. 702324
iterations 1288
Cbc0038I Pass 14: (2.70 seconds) suminf. 1.01152 (7) obj. 702324
iterations 819
Cbc0038I Pass 15: (2.80 seconds) suminf. 1.19475 (3) obj. 702324
iterations 829
Cbc0038I Pass 16: (2.97 seconds) suminf. 0.39164 (3) obj. 702324
iterations 1263
Cbc0038I Pass 17: (3.14 seconds) suminf. 2.72212 (14) obj. 702324
iterations 1157
Cbc0038I Pass 18: (3.23 seconds) suminf. 0.76161 (6) obj. 702324
iterations 642
Cbc0038I Pass 19: (3.33 seconds) suminf. 1.14048 (7) obj. 702324
iterations 676
Cbc0038I Pass 20: (3.35 seconds) suminf. 0.58538 (7) obj. 702324
iterations 65
Cbc0038I Pass 21: (3.45 seconds) suminf. 1.22497 (8) obj. 702324
iterations 819
Cbc0038I Pass 22: (3.55 seconds) suminf. 0.78393 (8) obj. 702324
iterations 695
Cbc0038I Pass 23: (3.62 seconds) suminf. 2.70611 (9) obj. 702324
iterations 498
Cbc0038I Pass 24: (3.71 seconds) suminf. 1.46133 (10) obj. 702324
iterations 734
Cbc0038I Pass 25: (3.86 seconds) suminf. 0.92747 (3) obj. 702324
iterations 1013
Cbc0038I Pass 26: (4.04 seconds) suminf. 0.39165 (3) obj. 702324
iterations 1259
Cbc0038I Pass 27: (4.19 seconds) suminf. 1.41464 (10) obj. 702324
iterations 1262
Cbc0038I Pass 28: (4.22 seconds) suminf. 1.34832 (11) obj. 702324
iterations 97
Cbc0038I Pass 29: (4.27 seconds) suminf. 0.88485 (7) obj. 702324
iterations 306
Cbc0038I Pass 30: (4.42 seconds) suminf. 0.39166 (3) obj. 702324
iterations 1137
Cbc0038I Pass 31: (4.56 seconds) suminf. 2.37535 (12) obj. 702324
iterations 1116
Cbc0038I Pass 32: (4.59 seconds) suminf. 1.88577 (9) obj. 702324
iterations 112
Cbc0038I Pass 33: (4.73 seconds) suminf. 1.53154 (7) obj. 702324
iterations 1058
Cbc0038I Rounding solution of 703116 is better than previous of 703170
Cbc0038I Before mini branch and bound, 459 integers at bound fixed and
7632 continuous
Cbc0038I Full problem 7700 rows 9620 columns, reduced to 365 rows 707
columns
Cbc0038I Mini branch and bound did not improve solution (4.79 seconds)
Cbc0038I Round again with cutoff of 701308
Cbc0038I Reduced cost fixing fixed 162 variables on major pass 4
Cbc0038I Pass 33: (4.80 seconds) suminf. 0.71082 (7) obj. 701308
iterations 0
Cbc0038I Pass 34: (4.87 seconds) suminf. 0.92631 (7) obj. 701308
iterations 475
Cbc0038I Pass 35: (4.98 seconds) suminf. 0.39166 (3) obj. 701308
iterations 874
Cbc0038I Pass 36: (5.09 seconds) suminf. 2.44643 (9) obj. 701308
iterations 986
Cbc0038I Pass 37: (5.12 seconds) suminf. 1.57924 (8) obj. 701308
iterations 173
Cbc0038I Pass 38: (5.18 seconds) suminf. 1.33638 (8) obj. 701308
iterations 420
Cbc0038I Pass 39: (5.24 seconds) suminf. 0.89980 (8) obj. 701308
iterations 338
Cbc0038I Pass 40: (5.26 seconds) suminf. 0.70149 (7) obj. 701308
iterations 3
Cbc0038I Pass 41: (5.31 seconds) suminf. 1.88387 (10) obj. 701308
iterations 329
Cbc0038I Pass 42: (5.41 seconds) suminf. 1.03977 (10) obj. 701308
iterations 625
Cbc0038I Pass 43: (5.50 seconds) suminf. 2.06700 (7) obj. 701308
iterations 714
Cbc0038I Pass 44: (5.52 seconds) suminf. 1.49926 (7) obj. 701308
iterations 42
Cbc0038I Pass 45: (5.63 seconds) suminf. 1.61967 (8) obj. 701308
iterations 859
Cbc0038I Pass 46: (5.67 seconds) suminf. 1.69794 (8) obj. 701308
iterations 274
Cbc0038I Pass 47: (5.75 seconds) suminf. 2.17072 (29) obj. 701308
iterations 400
Cbc0038I Pass 48: (5.82 seconds) suminf. 1.02394 (9) obj. 701308
iterations 549
Cbc0038I Pass 49: (5.94 seconds) suminf. 1.98728 (7) obj. 701308
iterations 940
Cbc0038I Pass 50: (5.95 seconds) suminf. 1.42064 (7) obj. 701308
iterations 35
Cbc0038I Pass 51: (6.05 seconds) suminf. 1.58112 (8) obj. 701308
iterations 875
Cbc0038I Pass 52: (6.10 seconds) suminf. 1.61924 (8) obj. 701308
iterations 298
Cbc0038I Pass 53: (6.17 seconds) suminf. 1.96594 (11) obj. 701308
iterations 369
Cbc0038I Pass 54: (6.25 seconds) suminf. 1.02399 (9) obj. 701308
iterations 662
Cbc0038I Pass 55: (6.34 seconds) suminf. 2.47790 (7) obj. 701308
iterations 736
Cbc0038I Pass 56: (6.36 seconds) suminf. 1.90543 (7) obj. 701308
iterations 66
Cbc0038I Pass 57: (6.46 seconds) suminf. 1.71261 (8) obj. 701308
iterations 725
Cbc0038I Pass 58: (6.48 seconds) suminf. 1.41015 (8) obj. 701308
iterations 42
Cbc0038I Pass 59: (6.54 seconds) suminf. 2.21785 (8) obj. 701308
iterations 457
Cbc0038I Pass 60: (6.61 seconds) suminf. 1.97975 (11) obj. 701308
iterations 390
Cbc0038I Pass 61: (6.72 seconds) suminf. 1.21160 (9) obj. 701308
iterations 731
Cbc0038I Pass 62: (6.82 seconds) suminf. 2.52607 (7) obj. 701308
iterations 783
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 452 integers at bound fixed and
7748 continuous
Cbc0038I Full problem 7700 rows 9620 columns, reduced to 437 rows 664
columns
Cbc0038I Mini branch and bound did not improve solution (6.88 seconds)
Cbc0038I After 6.88 seconds - Feasibility pump exiting with objective of
703116 - took 5.99 seconds
Cbc0012I Integer solution of 702815.79 found by feasibility pump after 0
iterations and 0 nodes (6.89 seconds)
Cbc0038I Full problem 7700 rows 9620 columns, reduced to 1722 rows 5619
columns
Cbc0012I Integer solution of 702578.94 found by RINS after 0 iterations
and 0 nodes (7.31 seconds)
Cbc0038I Full problem 7700 rows 9620 columns, reduced to 4473 rows 6682
columns - 168 fixed gives 1881, 5771 - ok now
Cbc0038I Full problem 7700 rows 9620 columns, reduced to 1706 rows 5600
columns
Cbc0031I 47 added rows had average density of 121.31915
Cbc0013I At root node, 47 cuts changed objective from 698939.26 to
701709.47 in 20 passes
Cbc0014I Cut generator 0 (Probing) - 632 row cuts average 2.6 elements,
140 column cuts (177 active) in 0.283 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 549 row cuts average 618.9 elements, 0
column cuts (10 active) in 0.132 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 3 row cuts average 2.7 elements, 0
column cuts (0 active) in 0.159 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0
column cuts (0 active) in 0.003 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 0 row cuts average 0.0
elements, 0 column cuts (0 active) in 0.073 seconds - new frequency is
-100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0
column cuts (0 active) in 0.214 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 141 row cuts average 194.2
elements, 0 column cuts (0 active) in 0.139 seconds - new frequency is
-100
Cbc0010I After 0 nodes, 1 on tree, 702578.94 best solution, best possible
701709.47 (9.65 seconds)
Cbc0012I Integer solution of 702567.06 found by rounding after 1662
iterations and 5 nodes (9.97 seconds)
Cbc0038I Full problem 7700 rows 9620 columns, reduced to 1735 rows 5630
columns
Cbc0001I Search completed - best objective 702567.060459936, took 1842
iterations and 6 nodes (10.17 seconds)
Cbc0032I Strong branching done 52 times (1466 iterations), fathomed 0
nodes and fixed 3 variables
Cbc0035I Maximum depth 4, 157 variables fixed on reduced cost
Cuts at root node changed objective from 698939 to 701709
Probing was tried 28 times and created 848 cuts of which 62 were active
after adding rounds of cuts (0.303 seconds)
Gomory was tried 28 times and created 572 cuts of which 21 were active
after adding rounds of cuts (0.151 seconds)
Knapsack was tried 20 times and created 3 cuts of which 0 were active
after adding rounds of cuts (0.159 seconds)
Clique was tried 20 times and created 0 cuts of which 0 were active after
adding rounds of cuts (0.003 seconds)
MixedIntegerRounding2 was tried 20 times and created 0 cuts of which 0
were active after adding rounds of cuts (0.073 seconds)
FlowCover was tried 20 times and created 0 cuts of which 0 were active
after adding rounds of cuts (0.214 seconds)
TwoMirCuts was tried 20 times and created 141 cuts of which 0 were active
after adding rounds of cuts (0.139 seconds)
Result - Optimal solution found
Objective value: 702567.06045994
Enumerated nodes: 6
Total iterations: 1842
Time (CPU seconds): 10.66
Time (Wallclock seconds): 10.66
Total time (CPU seconds): 10.66 (Wallclock seconds): 10.66
GLPK:
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 5.954e+004 ratio = 5.954e+004
GM: min|aij| = 2.215e-001 max|aij| = 4.515e+000 ratio = 2.038e+001
EQ: min|aij| = 4.923e-002 max|aij| = 1.000e+000 ratio = 2.031e+001
2N: min|aij| = 3.125e-002 max|aij| = 1.750e+000 ratio = 5.600e+001
Constructing initial basis...
GLPK Simplex Optimizer, v4.52
16115 rows, 18292 columns, 69897 non-zeros
Preprocessing...
9062 rows, 10877 columns, 55446 non-zeros
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 5.954e+004 ratio = 5.954e+004
GM: min|aij| = 2.220e-001 max|aij| = 4.504e+000 ratio = 2.029e+001
EQ: min|aij| = 4.935e-002 max|aij| = 1.000e+000 ratio = 2.026e+001
Constructing initial basis...
Size of triangular part is 9062
| 0: obj = -1.932515296e+024 infeas = 0.000e+000 (0)
| 500: obj = -1.154302628e+024 infeas = 2.650e-017 (0)
| 1000: obj = -2.781623320e+023 infeas = 2.082e-017 (0)
| 1500: obj = -1.155231990e+023 infeas = 0.000e+000 (0)
| 2000: obj = -1.105841400e+022 infeas = 0.000e+000 (0)
| 2500: obj = -2.352829508e+008 infeas = 1.426e-014 (0)
| 3000: obj = -6.022214966e+007 infeas = 1.991e-017 (0)
| 3500: obj = -2.720419317e+007 infeas = 3.002e-017 (0)
| 4000: obj = 6.974146751e+005 infeas = 1.869e-017 (0)
| 4434: obj = 6.989392611e+005 infeas = 2.429e-017 (0)
OPTIMAL LP SOLUTION FOUND
GLPK Integer Optimizer, v4.52
16115 rows, 18292 columns, 69897 non-zeros
1488 integer variables, all of which are binary
Integer optimization begins...
Gomory's cuts enabled
MIR cuts enabled
Cover cuts enabled
Clique cuts enabled
Constructing conflict graph...
No conflicts found
+ 4434: mip = not found yet >= -inf (1; 0)
Cuts on level 0: gmi = 57; mir = 24;
+ 4952: mip = not found yet >= 6.994485697e+005 (15; 2)
+ 5195: mip = not found yet >= 6.994485697e+005 (24; 9)
Cuts on level 24: gmi = 60; mir = 26;
+ 5279: >>>>> 4.799426989e+006 >= 6.994485697e+005 85.4% (25; 11)
+ 6126: mip = 4.799426989e+006 >= 7.018002846e+005 85.4% (44; 51)
Cuts on level 21: gmi = 64; mir = 31;
+ 6288: >>>>> 2.502268148e+006 >= 7.018002846e+005 72.0% (48; 55)
+ 6614: mip = 2.502268148e+006 >= 7.021170541e+005 71.9% (24; 141)
Cuts on level 19: gmi = 66; mir = 32;
+ 6667: >>>>> 7.025680633e+005 >= 7.021170541e+005 < 0.1% (25; 142)
Cuts on level 19: gmi = 66; mir = 32;
+ 6765: >>>>> 7.025678132e+005 >= 7.021170541e+005 < 0.1% (8; 193)
+ 6871: mip = 7.025678132e+005 >= 7.021170541e+005 < 0.1% (7; 210)
Cuts on level 19: gmi = 66; mir = 32;
+ 6878: >>>>> 7.025677132e+005 >= 7.021170541e+005 < 0.1% (7; 210)
Cuts on level 19: gmi = 66; mir = 32;
+ 6992: >>>>> 7.025674106e+005 >= 7.021170541e+005 < 0.1% (8; 227)
Cuts on level 19: gmi = 66; mir = 32;
+ 7090: >>>>> 7.025671605e+005 >= 7.021170541e+005 < 0.1% (7; 242)
+ 7196: mip = 7.025671605e+005 >= 7.021170541e+005 < 0.1% (6; 259)
Cuts on level 19: gmi = 66; mir = 32;
+ 7203: >>>>> 7.025670605e+005 >= 7.021170541e+005 < 0.1% (6; 259)
+ 7240: mip = 7.025670605e+005 >= tree is empty 0.0% (0; 285)
INTEGER OPTIMAL SOLUTION FOUND
--
Ticket URL: <https://projects.coin-or.org/SYMPHONY/ticket/122>
SYMPHONY <http://projects.coin-or.org/SYMPHONY>
The SYMPHONY framework for parallel branch-and-cut algorithms.
More information about the Symphony-tickets
mailing list