Re: [Bug-glpk] Another Bug in mip presolver?

[Andrew Makhorin]

> Some time ago I posted a bug report regarding a bug in the
> presolver. Somehow the attached model file vanished, so I assume it
> has been rejected due to its size. I tried to reproduce the error
> with a reduced model, but I didnt succeed on that, so I try again to
> send the original model file, this time gzipped.

> I encountered an error solving a medium-sized MIP (see attached file
> x3.mod). Using the standard options, glpk reports the attached problem
> to have no feasible solution, though it has by construction as well as
> according to a number of other LP solvers, namely lpsolve, CPLEX 10,
> COIN clp. Using either the interior point option or the --nopresol
> option, glpk finds the correct solution.

> The error does not seem to be related to the integer part, as it
> occurs in the relaxed problem (option --nomip) as well.

Thank you for your bug report.

It is an error, not a bug, which, in fact, appears in the lp presolver.
The constraint matrix is badly scaled, so the presolving (as implemented
in glpk) becomes unreliable.

Replacing tiny elements of the (assembled) constraint matrix whose
magnitude is less than 1e-7 by exact zeros resolves the problem:

Reading model section from x3.mod...
Reading data section from x3.mod...
4642 lines were read
Generating Z...
Generating C1...
Generating C2...
Generating C3...
Generating C4...
Generating XX0...
Generating XX1...
Generating XX2...
Generating XX3...
Generating XX4...
Model has been successfully generated
glp_simplex: original LP has 154 rows, 26 columns, 2433 non-zeros
glp_simplex: presolved LP has 136 rows, 24 columns, 2394 non-zeros
lpx_adv_basis: size of triangular part = 136
      0:   objval =   9.173591604e+01   infeas =   1.000000000e+00 (0)
    145:   objval =   5.863178719e+01   infeas =   0.000000000e+00 (0)
*   145:   objval =   5.863178719e+01   infeas =   0.000000000e+00 (0)
*   175:   objval =   5.102612443e+01   infeas =   4.440892099e-16 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+   175: mip =     not found yet >=              -inf        (1; 0)
+   177: >>>>>   5.106698778e+01 >=   5.102612443e+01 < 0.1% (2; 0)
+   181: mip =   5.106698778e+01 >=     tree is empty   0.0% (0; 3)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 1.1 Mb (1144307 bytes)

However, this leads to an inexact optimum (the correct optimal value
is 51.2365).