[Bug-glpk] Re: [Help-glpk] Incorrect result (bug) or programming issue?

[Andrew Makhorin]

> Incorrect result (bug) or programming issue?
> 
> I am rather new to ILP and even more to MathProg. I
> tried to write a simple
> example in MathProg, and use the glpk to solve an
> integer linear
> problem. Unfortunately the result is incorrect. One of
> the condition, i.e. in
> this case:
> 
> x3 + x4 <= 3
> 
> does not hold. The solver reports to find an optimal
> solution with x3 = -5,
> and x4 = 9. Thus x3 + x4 equals to 4 and is grater
> than 3. I used glpk-4.8
> and issue the flowing command:
> 
> $ glpsol --version
> GLPSOL -- GLPK LP/MIP Solver, Version 4.8
> Copyright (C) 2000, 01, 02, 03, 04 Andrew Makhorin
> <address@hidden>
> This program is free software; you may redistribute it
> under the terms of
> the GNU General Public License. This program has
> absolutely no warranty.
> 
> $ glpsol --math ex1.mod
> Reading model section from ex1.mod...
> 21 lines were read
> Generating r1...
> Generating r2...
> Generating r3...
> Generating r4...
> Generating obj...
> Model has been successfully generated
> lpx_simplex: original LP has 5 rows, 4 columns, 13
> non-zeros
> lpx_simplex: presolved LP has 4 rows, 4 columns, 9
> non-zeros
> lpx_adv_basis: size of triangular part = 4
> *     0:   objval =   0.000000000e+00   infeas =  
> 0.000000000e+00 (0)
> *     3:   objval =   1.750000000e+01   infeas =  
> 0.000000000e+00 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> Objective function is integral
> +     3: mip =     not found yet <=              +inf 
>       (1; 0)
> +     4: mip =   1.700000000e+01 <=   1.700000000e+01 
>  0.0% (2; 0)
> +     4: mip =   1.700000000e+01 <=     tree is empty 
>  0.0% (0; 3)
> INTEGER OPTIMAL SOLUTION FOUND
> Time used:   0.0 secs
> Memory used: 0.1M (151368 bytes)
> x1=0, x2=5, x3=-5, x4=9
> (obj: 17)
> Model has been successfully processed
> 
> where ex1.mod is:
> 
> $ cat ex1.mod 
> # EX1 --- starts here
var x1, integer, >>= 0;
var x2, integer, >>= 0;
> var x3, integer;
> var x4, integer;
> 
> subject to 
> r1: x1 + x2, <= 5;
> r2: x3 + x4, <= 3;
> r3: x1 - x3 + x4, <= 16;
> r4: 10 * x1 + 6 * x2, <= 45;
> 
> maximize obj: x1 + x2 + x3 + 2 * x4;
> 
> solve;
> 
> printf "x1=%d, x2=%d, x3=%d, x4=%d\n", x1, x2, x3, x4;
> printf "(obj: %d)\n", x1 + x2 + x3 + 2 * x4;
> 
> end;
> # EX1 --- ends here
> 
> First I wonder if the program is correctly written? If
> so, is it a bug in the solver?
> 

Thank you very much for your bug report.

The bug is not in the solver, but in the implementation of printf
statement. The solution output from glpsol (-o filename) indicates that
x3 = -6, not -5 as printed by printf.

I need a time to locate and fix the bug.

Andrew Makhorin


Problem:    bug
Rows:       5
Columns:    4 (4 integer, 0 binary)
Non-zeros:  13
Status:     INTEGER OPTIMAL
Objective:  obj = 17 (MAXimum) 17.5 (LP)

   No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 r1                          5                           5
     2 r2                          3                           3
     3 r3                         15                          16
     4 r4                         30                          45
     5 obj                        17

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 x1           *              0             0
     2 x2           *              5             0
     3 x3           *             -6
     4 x4           *              9

End of output