Re: [Bug-glpk] [ numerical instability & infinite loops ]

[Andrew Makhorin]

Thank you for the bug report.

> Please find attached a CPXLP filedescribing a MIP whose resolution
> implies an infinite loop during branch and bound (the algorithm loops
> ona basis when solving a LP relaxation). The resolution is done with
> GLPK 4.24, compiled on Win32 x86 withVC 8.0, with the default
> parameters.The same problem occurs withdifferent sets ofparameters
> (for example with --nopresol,orwith branching on mostfractional
> variable --mostf). The samebehavior is found when compilingwith GCC
> 3.4.4under Cygwin.

I could not reproduce the infinite loop. The underlying lp solver used
by the glpk mip solver is not robust, so the loop (as well as the crash)
might be caused by large objective coefficients and badly scaled
constraint matrix.

I belive that your instance is hard for the glpk mip solver. Using
`glpsol --noscale --mir' I could obtain a suboptimal solution to your
instance; however, due to excessive round-off errors the solver was
unable to finish the solution process:

glp_read_lp: reading problem data from `test.lp'...
glp_read_lp: 3581 rows, 3674 columns, 14387 non-zeros
glp_read_lp: 595 integer columns, all of which are binary
glp_read_lp: 7031 lines were read
ipp_basic_tech:  1939 row(s) and 1593 column(s) removed
ipp_reduce_bnds: 2 pass(es) made, 894 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 1642 rows, 2081 columns, 6838 non-zeros
lpx_intopt: 281 integer columns, all of which are binary
lpx_adv_basis: size of triangular part = 1641
Solving LP relaxation...
      0:   objval =   2.500315696e+12   infeas =   1.000000000e+00 (1)
     33:   objval =   1.409845061e+12   infeas =   0.000000000e+00 (0)
*    33:   objval =   1.409845061e+12   infeas =   0.000000000e+00 (0)
spx_prim_chuzc: recomputing basic solution components
*    88:   objval =   7.704330152e-18   infeas =   1.670780422e-14 (0)
OPTIMAL SOLUTION FOUND
Generating cutting planes...
&    88: obj =   7.704330152e-18   frac =    16   cuts =     0 (0)
&    88: obj =   7.704330152e-18   frac =    16   cuts =     0 (0)
Integer optimization begins...
+    88: mip =     not found yet >=              -inf        (1; 0)
MIR cuts enabled
+   458: mip =     not found yet >=   0.000000000e+00        (84; 0)
+   776: >>>>>   1.388724242e+07 >=   0.000000000e+00 100.0% (178; 0)
+  1113: mip =   1.388724242e+07 >=   0.000000000e+00 100.0% (261; 1)
+  1336: >>>>>   1.146831545e+07 >=   0.000000000e+00 100.0% (317; 1)
+  1764: mip =   1.146831545e+07 >=   0.000000000e+00 100.0% (372; 39)
+  2018: mip =   1.146831545e+07 >=   0.000000000e+00 100.0% (464; 40)
+  2101: >>>>>   6.624731892e+06 >=   0.000000000e+00 100.0% (510; 40)
+  2496: mip =   6.624731892e+06 >=   0.000000000e+00 100.0% (358; 496)
+  2869: mip =   6.624731892e+06 >=   0.000000000e+00 100.0% (444; 497)
+  3138: mip =   6.624731892e+06 >=   0.000000000e+00 100.0% (532; 498)
+  3225: >>>>>   4.401017034e+06 >=   0.000000000e+00 100.0% (579; 498)
. . . . . . . .
+198930: mip =   2.816773205e+04 >=   0.000000000e+00 100.0% (6338; 13223)
+199034: mip =   2.816773205e+04 >=   0.000000000e+00 100.0% (6379; 13223)
+199153: >>>>>   4.016252278e+00 >=   0.000000000e+00 100.0% (6418; 13223)
+199472: mip =   4.016252278e+00 >=   0.000000000e+00 100.0% (5414; 15258)
spx_simplex: warning: numerical instability (dual simplex)
+199813: mip =   4.016252278e+00 >=   0.000000000e+00 100.0% (5429; 15263)
+200101: mip =   4.016252278e+00 >=   0.000000000e+00 100.0% (5456; 15266)
spx_simplex: warning: numerical instability (dual simplex)
Time used: 2404.1 secs.  Memory used: 24.0 Mb.
spx_simplex: warning: numerical instability (dual simplex)
spx_simplex: warning: numerical instability (dual simplex)
+200605: mip =   4.016252278e+00 >=   0.000000000e+00 100.0% (5467; 15272)
spx_simplex: warning: numerical instability (dual simplex)
+200909: mip =   4.016252278e+00 >=   0.000000000e+00 100.0% (5467; 15274)
. . . . . . . .
+318124: mip =   4.016252278e+00 >=   0.000000000e+00 100.0% (10698; 16904)
+318239: mip =   4.016252278e+00 >=   0.000000000e+00 100.0% (10705; 16908)
spx_invert: the basis matrix is singular
spx_simplex: numerical problems with basis matrix
spx_simplex: sorry, basis recovery procedure not implemented yet
ios_driver: unable to solve current LP relaxation; glp_simplex returned 5
+318249: mip =   4.016252278e+00 >=   0.000000000e+00 100.0% (10705; 16908)
glp_intopt: cannot solve current LP relaxation 
Time used:   3994.7 secs
Memory used: 38.1 Mb (39912146 bytes)

> Note that in GLPK 4.24 the parameter LPX_K_ITLIMhas no more effect
> in MIP resolution.In effect, the iteration limit is
> notcorrectlypassedfrom the IOS structure to theLP structure, when
> solving theMIP relaxation at each node. Idem for the time limit with
> parameterLPX_K_TMLIM. (I madesomepatches in my GLPK version, but I
> think that my corrections arequite dirty).Please feel free to contact
> me if my report is not enough detailed.

The iteration limit is not passed to glp_intopt at all; it is used
only in glp_simplex. The time limit must work at least in 4.28.
If necessary, you could prematurely terminate the search by specifying
the appropriate relative gap.