[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Bug-glpk] Re: [Help-glpk] Incorrect result (bug) or programming issue?
From: |
Andrew Makhorin |
Subject: |
[Bug-glpk] Re: [Help-glpk] Incorrect result (bug) or programming issue? |
Date: |
Mon, 21 Mar 2005 15:22:19 +0300 |
> 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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Bug-glpk] Re: [Help-glpk] Incorrect result (bug) or programming issue?,
Andrew Makhorin <=