[Symphony] Alarming inefficiency
Francois Dionne
brainstorm at videotron.ca
Fri Aug 1 14:05:26 EDT 2008
Dear mailing list,
I have found an integer problem that Symphony has a hard time to solve, but
which is solved almost immediatly by glpk 4.29 .
You will find four files attached to this post; "symphony.MPS" is my problem
dumped to an MPS file. "symphony.out.txt" is the output of
symphony -F symphony.MPS
,aborted before finding a single feasible solution. "glpsol.nocuts.txt" is
the output of
glpsol symphony.MPS
,once again aborted before finding a single feasible solution.
"glpsol.withcuts.txt" is the output of
glpsol --intopt --cuts symphony.MPS
, which told me right away that there is no integer feasible solution.
Any ideas, any suggestions?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: symphony.MPS
Type: application/octet-stream
Size: 4305 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/symphony/attachments/20080801/96499518/attachment.obj>
-------------- next part --------------
*******************************************************
* This is SYMPHONY Version 5.1.8 *
* Copyright 2000-2008 Ted Ralphs and others *
* All Rights Reserved. *
* Distributed under the Common Public License 1.0 *
*******************************************************
Reading input file...
Solving...
done: 7542 left: 6665 ub: ?? lb: -171.33 time: 5
done: 15110 left: 13359 ub: ?? lb: -171.09 time: 10
done: 21495 left: 19026 ub: ?? lb: -170.77 time: 15
done: 26877 left: 23776 ub: ?? lb: -170.67 time: 20
done: 31949 left: 28252 ub: ?? lb: -170.67 time: 25
done: 36779 left: 32560 ub: ?? lb: -170.67 time: 30
done: 41516 left: 36709 ub: ?? lb: -170.58 time: 35
done: 46155 left: 40786 ub: ?? lb: -170.44 time: 40
done: 50697 left: 44700 ub: ?? lb: -170.35 time: 45
done: 55124 left: 48569 ub: ?? lb: -170.25 time: 50
done: 59503 left: 52390 ub: ?? lb: -170.14 time: 55
done: 63778 left: 56165 ub: ?? lb: -169.97 time: 60
done: 68043 left: 59890 ub: ?? lb: -169.76 time: 65
done: 72248 left: 63535 ub: ?? lb: -169.51 time: 70
done: 76342 left: 67169 ub: ?? lb: -169.33 time: 75
done: 80336 left: 70691 ub: ?? lb: -169.33 time: 80
done: 84400 left: 74243 ub: ?? lb: -169.33 time: 85
done: 88432 left: 77769 ub: ?? lb: -169.33 time: 90
done: 92486 left: 81243 ub: ?? lb: -169.33 time: 95
done: 96494 left: 84747 ub: ?? lb: -169.33 time: 100
done: 100487 left: 88248 ub: ?? lb: -169.33 time: 105
done: 104427 left: 91660 ub: ?? lb: -169.33 time: 110
done: 108343 left: 95100 ub: ?? lb: -169.33 time: 115
done: 112209 left: 98522 ub: ?? lb: -169.33 time: 120
done: 116118 left: 101981 ub: ?? lb: -169.33 time: 125
done: 119947 left: 105356 ub: ?? lb: -169.33 time: 130
done: 123737 left: 108672 ub: ?? lb: -169.33 time: 135
done: 127561 left: 112012 ub: ?? lb: -169.33 time: 140
done: 131300 left: 115317 ub: ?? lb: -169.33 time: 145
done: 135149 left: 118656 ub: ?? lb: -169.33 time: 150
-------------- next part --------------
glp_read_mps: reading problem data from `symphony.MPS'...
glp_read_mps: problem BLANK
glp_read_mps: 3 rows, 24 columns, 72 non-zeros
glp_read_mps: 24 integer columns, none of which are binary
glp_read_mps: 106 records were read
glp_simplex: original LP has 3 rows, 24 columns, 72 non-zeros
glp_simplex: presolved LP has 2 rows, 24 columns, 48 non-zeros
lpx_adv_basis: size of triangular part = 1
0: objval = 5.333333333e+00 infeas = 1.000000000e+00 (0)
3: objval = 9.333333333e+00 infeas = 0.000000000e+00 (0)
* 3: objval = 9.333333333e+00 infeas = 0.000000000e+00 (0)
* 26: objval = -1.753333333e+02 infeas = 0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 26: mip = not found yet >= -inf (1; 0)
+ 22173: mip = not found yet >= -1.726666667e+02 (17973; 1007)
+ 33914: mip = not found yet >= -1.719555556e+02 (27428; 1526)
+ 41154: mip = not found yet >= -1.713675214e+02 (33215; 1844)
+ 47722: mip = not found yet >= -1.713675214e+02 (38318; 2086)
+ 52435: mip = not found yet >= -1.713333333e+02 (42140; 2304)
+ 56306: mip = not found yet >= -1.713333333e+02 (45144; 2507)
+ 60040: mip = not found yet >= -1.713333333e+02 (48159; 2693)
+ 63183: mip = not found yet >= -1.713333333e+02 (50697; 2870)
+ 66670: mip = not found yet >= -1.713333333e+02 (53485; 3033)
+ 69894: mip = not found yet >= -1.713333333e+02 (56087; 3187)
+ 73281: mip = not found yet >= -1.713333333e+02 (58912; 3331)
Time used: 60.0 secs. Memory used: 17.9 Mb.
+ 76263: mip = not found yet >= -1.713333333e+02 (61361; 3470)
+ 78666: mip = not found yet >= -1.713333333e+02 (63214; 3606)
+ 81260: mip = not found yet >= -1.713333333e+02 (65359; 3734)
+ 83942: mip = not found yet >= -1.713333333e+02 (67512; 3856)
+ 86679: mip = not found yet >= -1.711555556e+02 (69686; 3976)
+ 89019: mip = not found yet >= -1.711555556e+02 (71512; 4094)
+ 91404: mip = not found yet >= -1.710158730e+02 (73302; 4209)
+ 93186: mip = not found yet >= -1.710158730e+02 (74718; 4324)
+ 95306: mip = not found yet >= -1.708395062e+02 (76375; 4435)
+ 97688: mip = not found yet >= -1.708253968e+02 (78078; 4542)
+ 99344: mip = not found yet >= -1.708253968e+02 (79373; 4648)
+101289: mip = not found yet >= -1.708253968e+02 (80902; 4750)
Time used: 120.0 secs. Memory used: 24.8 Mb.
+102851: mip = not found yet >= -1.708253968e+02 (82106; 4852)
+104540: mip = not found yet >= -1.708253968e+02 (83371; 4953)
+106437: mip = not found yet >= -1.708253968e+02 (84864; 5050)
+108169: mip = not found yet >= -1.708253968e+02 (86212; 5146)
+110146: mip = not found yet >= -1.708253968e+02 (87802; 5239)
+111927: mip = not found yet >= -1.708253968e+02 (89221; 5331)
+113
-------------- next part --------------
glp_read_mps: reading problem data from `symphony.MPS'...
glp_read_mps: problem BLANK
glp_read_mps: 3 rows, 24 columns, 72 non-zeros
glp_read_mps: 24 integer columns, none of which are binary
glp_read_mps: 106 records were read
ipp_basic_tech: 1 row(s) and 0 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech: 0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
lpx_intopt: presolved MIP has 2 rows, 24 columns, 48 non-zeros
lpx_intopt: 24 integer columns, none of which are binary
lpx_adv_basis: size of triangular part = 1
Solving LP relaxation...
0: objval = 5.333333333e+00 infeas = 1.000000000e+00 (0)
3: objval = 9.333333333e+00 infeas = 0.000000000e+00 (0)
* 3: objval = 9.333333333e+00 infeas = 0.000000000e+00 (0)
* 26: objval = -1.753333333e+02 infeas = 0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Creating the conflict graph...
The conflict graph is either empty or too big
Generating cutting planes...
& 26: obj = -1.753333333e+02 frac = 2 cuts = 0 (0)
& 26: obj = -1.753333333e+02 frac = 2 cuts = 0 (0)
Integer optimization begins...
+ 26: mip = not found yet >= -inf (1; 0)
Gomory's cuts enabled
MIR cuts enabled
+ 26: mip = not found yet >= tree is empty (0; 1)
PROBLEM HAS NO INTEGER FEASIBLE SOLUTION
Time used: 0.0 secs
Memory used: 0.1 Mb (81996 bytes)
More information about the Symphony
mailing list