Re: [Bug-glpk] glpsol 4.21 doesn't find the good solution

[Andrew Makhorin]

> Here's a problem for which glpsol 4.21 doesn't find the optimal
> solution ; in fact, it finds a solution with a better value (275.066)
> than the one obtained (282.566) with Cplex 10.0 or SCIP (0.90 or 1.00).

Thank you very much for the bug report.

The solver obtains the wrong result because your instance is
ill-conditioned; more exactly, some subproblem which appears in the
branch-and-bound process is ill-condition in the sense that solution
of its lp relaxation is highly sensitive to round-off errors in some
integer variables. This is seen from the solver output, where some
constraints are violated. Of course, this is a lack of glpk solver.

Decreasing tol_int to 1e-7 (against 1e-6 used by default) allowed me
solving your instance correctly (please see the log below).

Andrew Makhorin


lpx_read_freemps: reading problem data from `ngs.mps'...
lpx_read_freemps: problem ./zpl/mo
lpx_read_freemps: 1815 rows, 1334 columns, 6112 non-zeros
lpx_read_freemps: 138 integer columns, all of which are binary
lpx_read_freemps: 11086 records were read
glp_simplex: original LP has 1815 rows, 1334 columns, 6112 non-zeros
glp_simplex: presolved LP has 1708 rows, 1260 columns, 5266 non-zeros
lpx_adv_basis: size of triangular part = 1708
      0:   objval =   1.082250000e+03   infeas =   1.000000000e+00 (0)
      2:   objval =   1.182250000e+03   infeas =   2.230499560e-17 (0)
*     2:   objval =   1.182250000e+03   infeas =   4.907099033e-16 (0)
*   200:   objval =   5.981362143e+02   infeas =   6.403780617e-13 (0)
*   400:   objval =   2.052536850e+02   infeas =   3.531265447e-15 (0)
*   515:   objval =   1.770649850e+02   infeas =   5.312168723e-14 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+   515: mip =     not found yet >=              -inf        (1; 0)
+   784: >>>>>   5.239980000e+02 >=   1.770649850e+02  66.2% (27; 0)
+  1495: >>>>>   5.206500000e+02 >=   1.803833121e+02  65.4% (77; 4)
+  2076: >>>>>   5.025580000e+02 >=   1.929802940e+02  61.6% (109; 11)
+  3216: mip =   5.025580000e+02 >=   2.291957036e+02  54.4% (147; 40)
+  3304: >>>>>   4.225480000e+02 >=   2.291957036e+02  45.8% (152; 40)
+  3771: >>>>>   3.037460000e+02 >=   2.308067238e+02  24.0% (116; 156)
+  4992: mip =   3.037460000e+02 >=   2.442145800e+02  19.6% (127; 271)
+  5181: >>>>>   2.910660000e+02 >=   2.469456184e+02  15.2% (141; 271)
+  6112: mip =   2.910660000e+02 >=   2.489145800e+02  14.5% (149; 370)
+  7328: mip =   2.910660000e+02 >=   2.532529911e+02  13.0% (200; 387)
+  8290: mip =   2.910660000e+02 >=   2.576962873e+02  11.5% (255; 406)
+  9526: mip =   2.910660000e+02 >=   2.599965800e+02  10.7% (294; 430)
+ 10597: mip =   2.910660000e+02 >=   2.623465800e+02   9.9% (344; 452)
+ 11708: mip =   2.910660000e+02 >=   2.637145800e+02   9.4% (388; 475)
+ 12800: mip =   2.910660000e+02 >=   2.648465800e+02   9.0% (439; 494)
+ 13841: mip =   2.910660000e+02 >=   2.661290000e+02   8.6% (493; 515)
+ 15195: mip =   2.910660000e+02 >=   2.674840000e+02   8.1% (527; 541)
+ 16417: mip =   2.910660000e+02 >=   2.686614200e+02   7.7% (570; 563)
+ 17607: mip =   2.910660000e+02 >=   2.696131391e+02   7.4% (622; 581)
+ 18816: mip =   2.910660000e+02 >=   2.707709911e+02   7.0% (664; 605)
+ 20086: mip =   2.910660000e+02 >=   2.716381600e+02   6.7% (701; 631)
+ 21599: mip =   2.910660000e+02 >=   2.732437191e+02   6.1% (715; 666)
+ 22935: mip =   2.910660000e+02 >=   2.742471386e+02   5.8% (739; 700)
+ 24375: mip =   2.910660000e+02 >=   2.750296112e+02   5.5% (759; 732)
+ 25325: >>>>>   2.901860000e+02 >=   2.762145800e+02   4.8% (770; 771)
+ 25341: >>>>>   2.900660000e+02 >=   2.762145800e+02   4.8% (744; 828)
+ 25478: >>>>>   2.851860000e+02 >=   2.762145800e+02   3.1% (741; 845)
+ 26300: mip =   2.851860000e+02 >=   2.768584288e+02   2.9% (491; 1429)
+ 27200: mip =   2.851860000e+02 >=   2.780060488e+02   2.5% (495; 1521)
+ 28128: mip =   2.851860000e+02 >=   2.789471386e+02   2.2% (444; 1672)
+ 28286: >>>>>   2.840660000e+02 >=   2.792584288e+02   1.7% (442; 1697)
+ 29032: >>>>>   2.830660000e+02 >=   2.802347483e+02   1.0% (313; 2100)
+ 29742: mip =   2.830660000e+02 >=   2.811300800e+02   0.7% (188; 2573)
+ 30208: >>>>>   2.827460000e+02 >=   2.815620000e+02   0.4% (163; 2668)
+ 30252: >>>>>   2.825660000e+02 >=   2.815620000e+02   0.4% (123; 2805)
+ 30716: mip =   2.825660000e+02 >=   2.823614200e+02 < 0.1% (12; 3295)
+ 30761: mip =   2.825660000e+02 >=     tree is empty   0.0% (0; 3439)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   136.0 secs
Memory used: 8.4 Mb (8798707 bytes)