help-glpk
[Top][All Lists]

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

 From: Andrzej BEDNARSKI Subject: [Help-glpk] Incorrect result (bug) or programming issue? Date: Mon, 21 Mar 2005 00:53:11 -0800 (PST)

```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
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
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
(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

```