Re: [Help-glpk] MIP presolver and dual simplex in root relaxation

[Andrew Makhorin]

> Here is a mathprog-file that behaves as I described.

Thank you. I was able to reproduce the behavior.

JFYI: Numerical instability in the primal simplex happens because the
choice of a pivot on some steps leads to a badly conditioned basis and
as a result to non-accurate intermediate solutions. Unfortunately, this
situation repeats, so the solver makes no progress. In 4.56 (I plan to
release it on a next week) the choice of a pivot was significantly
improved that, in particular, allows successfully solving lp relaxation
of your model with the primal simplex:

[...]
Model has been successfully generated
GLPK Integer Optimizer, v4.56
16108 rows, 3048 columns, 45035 non-zeros
640 integer variables, all of which are binary
Preprocessing...
178 hidden packing inequaliti(es) were detected
3397 hidden covering inequaliti(es) were detected
13363 rows, 2464 columns, 39922 non-zeros
616 integer variables, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  2.000e+02  ratio =  2.000e+02
GM: min|aij| =  2.777e-01  max|aij| =  3.601e+00  ratio =  1.297e+01
EQ: min|aij| =  8.052e-02  max|aij| =  1.000e+00  ratio =  1.242e+01
2N: min|aij| =  6.250e-02  max|aij| =  1.563e+00  ratio =  2.500e+01
Constructing initial basis...
Size of triangular part is 13363
Solving LP relaxation...
GLPK Simplex Optimizer, v4.56
13363 rows, 2464 columns, 39922 non-zeros
      0: obj =   1.065000000e+04 inf =   1.913e+03 (152)
    500: obj =   4.533632000e+04 inf =   2.347e+02 (49) 4
   1000: obj =   4.864335130e+04 inf =   1.398e+02 (39) 4
   1500: obj =   5.829885308e+04 inf =   1.800e+00 (1) 4
   1986: obj =   5.912682259e+04 inf =   1.330e-08 (0) 5
*  2000: obj =   5.734685000e+04 inf =   1.329e-08 (153)
*  2500: obj =   5.388243299e+04 inf =   2.667e-08 (28) 5
Warning: numerical instability (primal simplex, phase II)
   2578: obj =   5.388200910e+04 inf =   3.413e-08 (0) 2
Warning: numerical instability (primal simplex, phase II)
   2590: obj =   5.388200910e+04 inf =   3.413e-08 (0) 2
Warning: numerical instability (primal simplex, phase II)
   2597: obj =   5.388200910e+04 inf =   2.667e-08 (0) 2
Warning: numerical instability (primal simplex, phase II)
   2606: obj =   5.388200910e+04 inf =   2.667e-08 (0) 2
Warning: numerical instability (primal simplex, phase II)
   2615: obj =   5.388200910e+04 inf =   2.667e-08 (0) 2
Warning: numerical instability (primal simplex, phase II)
   2624: obj =   5.388200910e+04 inf =   8.747e-08 (0) 2
Warning: numerical instability (primal simplex, phase II)
   2633: obj =   5.388200910e+04 inf =   2.667e-08 (0) 2
*  2690: obj =   5.387742948e+04 inf =   2.560e-08 (0) 1
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
[...]
Cuts on level 8: gmi = 10; mir = 155; cov = 1;
+  2944: >>>>>   5.618500000e+04 >=   5.609219943e+04   0.2% (6; 11)
+  3033: mip =   5.618500000e+04 >=     tree is empty   0.0% (0; 25)
INTEGER OPTIMAL SOLUTION FOUND