[Bug-glpk] [Fwd: I have a problem with glpk]

[Andrew Makhorin]

-------- Forwarded Message --------
From: "Ágoston Kolos" <address@hidden>
To: address@hidden
Subject: I have a problem with glpk
Date: Wed, 17 Apr 2013 12:56:45 +0200

 Dear Develpers,

I have use GLPK since several year, and I am very satisfied with it. I
would like to thank your work!
Recently I discovered a problem. A use standalone version 4.34 on a
Windows XP

> glpsol -v
GLPSOL: GLPK LP/MIP Solver 4.34

Copyright (C) 2008 Andrew Makhorin, Department for Applied Informatics,
Moscow Aviation Institute, Moscow, Russia. All rights reserved.

This program has ABSOLUTELY NO WARRANTY.

This program is free software; you may re-distribute it under the terms
of the GNU General Public License version 3 or later.

I tried to solve a mixed integer LP (attached as lp0.txt). The problem
said that is has not integer solution:

> glpsol --cpxlp lp0.txt
glp_read_lp: reading problem data from `lp0.txt'...
glp_read_lp: 132 rows, 150 columns, 332 non-zeros
glp_read_lp: 33 integer columns, all of which are binary
glp_read_lp: 231 lines were read
ipp_basic_tech:  4 row(s) and 5 column(s) removed
ipp_reduce_bnds: 29 pass(es) made, 85 bound(s) reduced
ipp_basic_tech:  1 row(s) and 1 column(s) removed
ipp_reduce_coef: 2 pass(es) made, 1 coefficient(s) reduced
glp_intopt: presolved MIP has 127 rows, 144 columns, 323 non-zeros
glp_intopt: 30 integer columns, all of which are binary
Scaling...
 A: min|aij| = 1.000e+000  max|aij| = 1.000e+008  ratio = 1.000e+008
GM: min|aij| = 1.000e+000  max|aij| = 1.000e+000  ratio = 1.000e+000
EQ: min|aij| = 1.000e+000  max|aij| = 1.000e+000  ratio = 1.000e+000
2N: min|aij| = 7.451e-001  max|aij| = 1.170e+000  ratio = 1.571e+000
Crashing...
Size of triangular part = 127
Solving LP relaxation...
      0: obj = -7.341498715e+003  infeas = 6.319e+007 (0)
*    41: obj =  3.797002300e+004  infeas = 0.000e+000 (0)
*    78: obj =  2.983881319e+004  infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+    78: mip =     not found yet >=              -inf        (1; 0)
+    78: mip =     not found yet >=     tree is empty        (0; 1)
PROBLEM HAS NO INTEGER FEASIBLE SOLUTION
Time used:   0.0 secs
Memory used: 0.2 Mb (254740 bytes)

I modified the problem: I attached a new constraint F4=1 (lp1.txt) and
the program solve the MLP:

> glpsol --cpxlp lp1.txt
glp_read_lp: reading problem data from `lp1.txt'...
glp_read_lp: 133 rows, 150 columns, 333 non-zeros
glp_read_lp: 33 integer columns, all of which are binary
glp_read_lp: 231 lines were read
ipp_basic_tech:  6 row(s) and 6 column(s) removed
ipp_reduce_bnds: 30 pass(es) made, 84 bound(s) reduced
ipp_basic_tech:  1 row(s) and 1 column(s) removed
ipp_reduce_coef: 2 pass(es) made, 1 coefficient(s) reduced
glp_intopt: presolved MIP has 126 rows, 143 columns, 321 non-zeros
glp_intopt: 29 integer columns, all of which are binary
Scaling...
 A: min|aij| = 1.000e+000  max|aij| = 1.000e+008  ratio = 1.000e+008
GM: min|aij| = 1.000e+000  max|aij| = 1.000e+000  ratio = 1.000e+000
EQ: min|aij| = 1.000e+000  max|aij| = 1.000e+000  ratio = 1.000e+000
2N: min|aij| = 7.451e-001  max|aij| = 1.170e+000  ratio = 1.571e+000
Crashing...
Size of triangular part = 126
Solving LP relaxation...
      0: obj =  2.658501285e+003  infeas = 6.319e+007 (0)
*    41: obj =  4.758082980e+004  infeas = 0.000e+000 (0)
*    78: obj =  3.944961999e+004  infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+    78: mip =     not found yet >=              -inf        (1; 0)
+    78: >>>>>  3.944961999e+004 >=  3.944961999e+004   0.0% (1; 0)
+    78: mip =  3.944961999e+004 >=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.2 Mb (246161 bytes)

However the optimal solution to the second problem is a feasible
solution for the firt problem, so I am confused. Is there something I
left out of consideration?

Thank your answer!
Best wishes:

Kolos

lp0.txt
Description: Text document

lp1.txt
Description: Text document