Re: [Bug-glpk] [Fwd: MIP solver bug]

[Chris Matrakidis]

Hi Emma,

> The attached example can be solved quickly in 4.56 but not in 4.57 and 
> afterwards.

Starting with version 4.56 Andrew is improving the solver routines,
however I don't think this is the issue here.

Using GLPK 4.60 (the latest released version), I can quickly solve
your problem with pseudocost brancing, However if I disable the MIP
presolver (--nointopt) I get a different solution, which is strongly
indicating accuracy issues. Indeed the line:
A: min|aij| = 2.451e-011  max|aij| = 1.158e+077  ratio = 4.724e+087
indicates that there are some very large values in the problem, which
can cause problems like this. Is this a big M formulation like the one
you showed last week?

Best Regards,

Chris Matrakidis

PS. The output from the first run is:

GLPSOL: GLPK LP/MIP Solver, v4.60
Parameter(s) specified in the command line:
 --pcost --glp \Users\Chris\Downloads\lp.txt
Reading problem data from '\Users\Chris\Downloads\lp.txt'...
332 rows, 190 columns, 5043 non-zeros
95 integer variables, all of which are binary
5563 lines were read
GLPK Integer Optimizer, v4.60
332 rows, 190 columns, 5043 non-zeros
95 integer variables, all of which are binary
Preprocessing...
95 constraint coefficient(s) were reduced
154 rows, 190 columns, 3899 non-zeros
95 integer variables, all of which are binary
Scaling...
 A: min|aij| = 1.307e-009  max|aij| = 7.569e+005  ratio = 5.792e+014
GM: min|aij| = 1.939e-004  max|aij| = 5.157e+003  ratio = 2.659e+007
EQ: min|aij| = 3.761e-008  max|aij| = 1.000e+000  ratio = 2.659e+007
2N: min|aij| = 4.643e-008  max|aij| = 1.710e+000  ratio = 3.684e+007
Constructing initial basis...
Size of triangular part is 154
Solving LP relaxation...
GLPK Simplex Optimizer, v4.60
154 rows, 190 columns, 3899 non-zeros
      0: obj =  1.934670808e+006 inf =  1.688e+005 (93)
    231: obj =  1.673470251e-009 inf =  1.269e-015 (0) 1
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
+   231: mip =     not found yet >=              -inf        (1; 0)
Warning: numerical instability (dual simplex, phase II)
+ 15741: >>>>>  3.256673153e-008 >=  1.666194294e-009  94.9% (20; 368)
+ 15741: mip =  3.256673153e-008 >=     tree is empty   0.0% (0; 583)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   1.4 secs
Memory used: 1.2 Mb (1220521 bytes)


Without MIP presolving:

GLPSOL: GLPK LP/MIP Solver, v4.60
Parameter(s) specified in the command line:
 --pcost --glp \Users\Chris\Downloads\lp.txt --nointopt
Reading problem data from '\Users\Chris\Downloads\lp.txt'...
332 rows, 190 columns, 5043 non-zeros
95 integer variables, all of which are binary
5563 lines were read
Scaling...
 A: min|aij| = 2.451e-011  max|aij| = 1.158e+077  ratio = 4.724e+087
GM: min|aij| = 1.939e-004  max|aij| = 5.157e+003  ratio = 2.659e+007
EQ: min|aij| = 3.761e-008  max|aij| = 1.000e+000  ratio = 2.659e+007
Constructing initial basis...
Size of triangular part is 328
GLPK Simplex Optimizer, v4.60
332 rows, 190 columns, 5043 non-zeros
Preprocessing...
154 rows, 190 columns, 3899 non-zeros
Scaling...
 A: min|aij| = 1.307e-009  max|aij| = 1.158e+077  ratio = 8.862e+085
GM: min|aij| = 1.939e-004  max|aij| = 5.157e+003  ratio = 2.659e+007
EQ: min|aij| = 3.761e-008  max|aij| = 1.000e+000  ratio = 2.659e+007
Constructing initial basis...
Size of triangular part is 154
      0: obj =  1.934670808e+006 inf =  1.884e+045 (1)
      4: obj =  1.934670808e+006 inf =  1.394e-026 (0)
*    76: obj = -3.027563880e+006 inf =  4.264e-027 (0)
OPTIMAL LP SOLUTION FOUND
GLPK Integer Optimizer, v4.60
332 rows, 190 columns, 5043 non-zeros
95 integer variables, all of which are binary
Integer optimization begins...
+    76: mip =     not found yet >=              -inf        (1; 0)
+    76: >>>>> -3.027563880e+006 >= -3.027563880e+006   0.0% (1; 0)
+    76: mip = -3.027563880e+006 >=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.1 secs
Memory used: 0.6 Mb (603108 bytes)