[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] 4.39 fails to produde optimal solution
From: |
Andrew Makhorin |
Subject: |
Re: [Bug-glpk] 4.39 fails to produde optimal solution |
Date: |
Fri, 28 Aug 2009 17:08:27 +0400 |
Looks like large constraint coefficients cause the effect described
in the paper:
A. Neumaier and O. Shcherbina, Safe bounds in linear and mixed-integer
programming, Math. Programming A 99 (2004), 283-296.
http://www.mat.univie.ac.at/~neum/ms/mip.pdf
when tightening the feasible region "improves" the optimum.
In particular, if MIR or Gomory mixed integer cuts are enabled, glpsol
finds the correct solution:
$ glpsol --cpxlp glpkin.txt --mir
GLPSOL: GLPK LP/MIP Solver 4.40
Reading problem data from `glpkin.txt'...
12 rows, 48 columns, 216 non-zeros
48 integer variables, all of which are binary
178 lines were read
ipp_basic_tech: 0 row(s) and 0 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 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
glp_intopt: presolved MIP has 12 rows, 48 columns, 216 non-zeros
glp_intopt: 48 integer columns, all of which are binary
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 5.040e+07 ratio = 5.040e+07
GM: min|aij| = 6.708e-01 max|aij| = 1.491e+00 ratio = 2.222e+00
EQ: min|aij| = 4.650e-01 max|aij| = 1.000e+00 ratio = 2.151e+00
2N: min|aij| = 2.500e-01 max|aij| = 1.439e+00 ratio = 5.758e+00
Constructing initial basis...
Size of triangular part = 12
Solving LP relaxation...
* 0: obj = 5.975086563e+04 infeas = 0.000e+00 (0)
* 23: obj = 4.295331243e+04 infeas = 0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
MIR cuts enabled
+ 23: mip = not found yet >= -inf (1; 0)
+ 63: >>>>> 4.296612894e+04 >= 4.295331243e+04 < 0.1% (7; 0)
+ 64: >>>>> 4.295674010e+04 >= 4.295331243e+04 < 0.1% (5; 3)
+ 65: >>>>> 4.295528707e+04 >= 4.295331243e+04 < 0.1% (4; 5)
+ 80: >>>>> 4.295372226e+04 >= 4.295346307e+04 < 0.1% (2; 8)
+ 84: mip = 4.295372226e+04 >= tree is empty 0.0% (0; 13)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.2 Mb (162716 bytes)