[Symphony] Alarming inefficiency
Ashutosh Mahajan
asm4 at lehigh.edu
Fri Aug 1 15:40:13 EDT 2008
hi Fracois,
the problem has a constraint:
3 x0 -3 x1 + 3 x2 -3 x3 + 3 x4 -3 x5 + 3 x6 -3 x7 + 3 x8 -3 x9
+ 3 x10 -3 x11 + 3 x12 -3 x13 + 3 x14 -3 x15 + 3 x16 -3 x17 + 3 x18 -3 x19
+ 3 x20 -3 x21 + 3 x22 -3 x23 = -2
this straightaway makes the problem infeasible because left hand side can only
assume values in multiples of 3. it is easy to detect this in a preprocessing
stage but unfortunately symphony does not have a preprocessor yet.
i tried running the same problem on cplex-10 with preprocessor turned off and it
also starts generating many nodes.
hopefully we will have a preprocessor soon. however, even then it will be easy
to hide such constraints so that the preprocessor doesnt detect the
infeasibility easily.
ashutosh
On Fri, 01 Aug 2008, Francois Dionne wrote:
> 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?
>
> *******************************************************
> * 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
> 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
> 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)
> _______________________________________________
> Symphony mailing list
> Symphony at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/symphony
--
regards
Ashutosh Mahajan
http://coral.ie.lehigh.edu/~asm4
More information about the Symphony
mailing list