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

[Andrzej BEDNARSKI]

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?

-- 
Andy



                
__________________________________ 
Do you Yahoo!? 
Yahoo! Mail - Helps protect you from nasty viruses. 
http://promotions.yahoo.com/new_mail