Re: [Bug-glpk] preprocessing goes into infinite loop

[Andrew Makhorin]

> I work with the Sage computer algebra system, which can use GLPK as a
>  backend to solve mixed integer linear programs. Unfortunately, Sage
>  sometimes crashes when I am trying to solve some linear systems that
>  are machine-generated for a problem of interest to me.
> 
> I managed to reproduce one of these problems directly in GLPK, linking
>  via C++. I have placed a copy of the program at
> 
>     www.math.usm.edu/perry/glpk_bug.cpp
> 
> The problem creates an LP w/45 rows and 5 columns that apparently sends
>  GLPK's preprocessing into an infinite loop. If the 45th row is not
>  added (comment out the BOOM macro at the beginning of the file) then
>  the LP finds a solution.
> 
> We believe this is a bug in GLPK. If it is a problem with how we are
>  accessing GLPK from Sage, please let us know.
> 

Thank you for your bug report.

In fact, this is a bug in the glpk mip preprocessor. Using your code I
converted your mip instance in a text format and then tried to solve it
with glpsol:

GLPSOL: GLPK LP/MIP Solver, v4.47
Parameter(s) specified in the command line:
 --glp bug.lp
Reading problem data from `bug.lp'...
45 rows, 5 columns, 123 non-zeros
5 integer variables, none of which are binary
180 lines were read
GLPK Integer Optimizer, v4.47
45 rows, 5 columns, 123 non-zeros
5 integer variables, none of which are binary
Preprocessing...

EXCEPTION AT 0048A35B - FLOATING-POINT OVERFLOW (C0000091)
0048A35B 00003ADF 0048687C libglpk.a(glpnpp03.o)

EAX 0024A5F0   EBX 002462A8   ECX 0024A1C8   EDX 0024A9D8
ESI 00000000   EDI 00000014   EBP 0022F178   ESP 0022F150
CS 001B   DS 0023   SS 0023   ES 0023   FS 003B   GS 0000
EIP 0048A31C   EFLAGS 00010287

Program abnormally terminated

Call traceback
0048A31C 00003AA0 0048687C libglpk.a(glpnpp03.o)
0043F20C 000007F8 0043EA14 libglpk.a(glpnpp05.o)
0043F155 00000741 0043EA14 libglpk.a(glpnpp05.o)
0043F652 00000C3E 0043EA14 libglpk.a(glpnpp05.o)
0043F7B7 00000DA3 0043EA14 libglpk.a(glpnpp05.o)
004190BA 000004E6 00418BD4 libglpk.a(glpapi09.o)
0041A113 0000153F 00418BD4 libglpk.a(glpapi09.o)
00404DBC 00003D68 00401054 libglpk.a(glpapi21.o)
0040104C 00000038 00401014 glpsol.o
004BB607 00000D9B 004BA86C libc.a(xmain.o)
0040100B 0000000B 00401000 xstart.o
7C817067 ******** ********
End of traceback

The floating-point overflow happens in the routine npp_implied_bounds
(glpnpp03.c), which computes implied bounds of columns (variables), and
since on most platforms (including yours) this exception is usually
masked, glpk falls into infinite loop because of Inf/NaN.

The bug itself happens, because your mip instance has no integer
feasible solution and includes integer variables having no upper bound,
so the mip preprocessor attempts to infinitely increase lower bounds of
those variables with no success.

To avoid the bug you need to provide both lower and upper bounds for
every integer variable in the mip instance.


Andrew Makhorin