Bug#490288: glpk: Fails on assertion
Hi Rafael, Sorry for a delay in my response. I just tried GLPK 4.30 and it seems that the bug is still present (see below). Am I doing something wrong, or is the bug really not fixed yet? The bug really was not fixed in 4.30, because it appears due to excessive round-off errors in other routine (which provides solution of current lp relaxation and which should be replaced by a more robust version). I hope to resolve the issue in 4.31. Andrew Makhorin -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Bug#490288: glpk: Fails on assertion
[ This is in the context of: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=490288 ] * Andrew Makhorin [EMAIL PROTECTED] [2008-07-12 18:06]: Saturday, July 12, 2008, 5:56:31 PM, you wrote: Does this mean that the problem is in the formulation of that specific example or is it a bug in GLPK? If the later is the case, are you planning to fix it? It is a bug in the sense that the mip solver should return GLP_EFAIL rather than cause abnormal termination. The bug will be fixed in a next version of the package. I just tried GLPK 4.30 and it seems that the bug is still present (see below). Am I doing something wrong, or is the bug really not fixed yet? Cheers, Rafael === $ cat /var/tmp/bug.mod var x1 integer; var x2 integer; minimize objective : x1 + x2; s.t. constraint : (8^4 - 1) * x1 - 8^4 * x2 = 0; s.t. x1NotNegative : x1 = 1; s.t. x2NotNegative : x2 = 1; end; $ glpsol -m /var/tmp/bug.mod -o /var/tmp/bug.sol Reading model section from /var/tmp/bug.mod... 11 lines were read Generating objective... Generating constraint... Generating x1NotNegative... Generating x2NotNegative... Model has been successfully generated glp_simplex: original LP has 4 rows, 2 columns, 6 non-zeros Objective value = 2.0002442 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... + 0: mip = not found yet = -inf(1; 0) Assertion failed: x = lb Error detected in file glpios03.c at line 257 Aborted $ glpsol --version | grep GLPSOL GLPSOL: GLPK LP/MIP Solver 4.30 -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Bug#490288: [Bug-glpk] Re: [Pkg-scicomp-devel] Bug#490288: glpk: Fails on assertion
Hello Gernot, The modified example suggested by Andrew results in another failed assertion Assertion failed: ipp != ipp Error detected in file glpipp02.c at line 801 even in cases where the program without --cuts succeeds. a bug has been fixed in glpipp02.c in version 4.29 of GLPK. See http://lists.gnu.org/archive/html/bug-glpk/2008-04/msg7.html Best regards Xypron -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Bug#490288: [Pkg-scicomp-devel] Bug#490288: glpk: Fails on assertion
[ I'm a colleague of Ingo Feinerer working on the same topic. ] It seems that the behaviour of glpsol and the mip solver depend on the computer architecture and that the program doesn't always catch overflows or underflows. The modified example suggested by Andrew results in another failed assertion Assertion failed: ipp != ipp Error detected in file glpipp02.c at line 801 even in cases where the program without --cuts succeeds. Best regards, Gernot Context: GLPK LP/MIP Solver 4.28 Linux kernel 2.6.22-3-686 #1 SMP dual core Intel(R) Pentium(R) D CPU 2.80GHz stepping 07 $ cat f.mod var x1 integer, = 1, = 2500; var x2 integer, = 1, = 2500; minimize objective : x1 + x2; s.t. constraint : (7^4 - 1) * x1 - 7^4 * x2 = 0; end; $ glpsol -m f.mod -o f.sol Reading model section from f.mod... 5 lines were read Generating objective... Generating constraint... Model has been successfully generated glp_simplex: original LP has 2 rows, 2 columns, 4 non-zeros Objective value = 2.000416667 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... + 0: mip = not found yet = -inf(1; 0) + 2986:4.80100e+03 = 2.000416667e+00 100.0% (2988; 0) + 2986: mip = 4.80100e+03 = tree is empty 0.0% (0; 5975) INTEGER OPTIMAL SOLUTION FOUND Time used: 2.7 secs Memory used: 0.9 Mb (961737 bytes) lpx_print_mip: writing MIP problem solution to `f.sol'... $ glpsol -m f.mod --cuts -o f.sol Reading model section from f.mod... 5 lines were read Generating objective... Generating constraint... Model has been successfully generated ipp_basic_tech: 1 row(s) and 0 column(s) removed Assertion failed: ipp != ipp Error detected in file glpipp02.c at line 801 Aborted On Sat, Jul 12, 2008 at 04:06:52PM +0400, Andrew Makhorin wrote: Saturday, July 12, 2008, 12:35:26 PM, you wrote: package glpk tags 490288 confirmed upstream thanks * Ingo Feinerer [EMAIL PROTECTED] [2008-07-11 12:00]: Package: glpk Version: 4.11-1 Severity: normal The following linear program triggers an assertion and stops the program without a proper solution: var x1 integer; var x2 integer; minimize objective : x1 + x2; s.t. constraint : (8^4 - 1) * x1 - 8^4 * x2 = 0; s.t. x1NotNegative : x1 = 1; s.t. x2NotNegative : x2 = 1; end; Output of above program: [EMAIL PROTECTED]:~$ glpsol -m bug.mod -o bug.sol Reading model section from bug.mod... 11 lines were read Generating objective... Generating constraint... Generating x1NotNegative... Generating x2NotNegative... Model has been successfully generated lpx_simplex: original LP has 4 rows, 2 columns, 6 non-zeros Objective value = 2.0002442 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... Objective function is integral + 0: mip = not found yet = -inf(1; 0) + 6922: mip = not found yet = 3.0e+00(6924; 0) Assertion failed: x = lb; file glpmip2.c; line 230 I confirm the problem with glpk 4.29, which has just been uploaded to unstable. The error message is slightly different: Reading model section from bug.mod... 11 lines were read Generating objective... Generating constraint... Generating x1NotNegative... Generating x2NotNegative... Model has been successfully generated glp_simplex: original LP has 4 rows, 2 columns, 6 non-zeros Objective value = 2.0002442 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... + 0: mip = not found yet = -inf(1; 0) Assertion failed: x = lb Error detected in file glpios03.c at line 257 Aborted I am therefore forwarding this bug report to the upstream author. Andrew: could you please look at this? Please, respect the Reply-To when replying to this message. Thanks, Thank you for the bug report. The failure appears due to insufficient robustness of the glpk mip solver. It is mainly caused by unbounded integer variables (x1 and x2 have no upper bound) having relatively large coefficients in the constraint that leads to excessive round-off errors on solving LP relaxation. Unfortunately, I cannot reproduce the failure on my machine: $ glpsol -m bug.mod Reading model section from bug.mod... 11 lines were read Generating objective... Generating constraint... Generating x1NotNegative... Generating x2NotNegative... Model has been successfully generated glp_simplex: original LP has 4 rows, 2 columns, 6 non-zeros Objective value = 2.0002442 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... + 0: mip = not found yet = -inf(1; 0) + 2237: mip = not found yet = 2.000244200e+00(2242; 0) + 3113: mip = not found yet = 2.000244200e+00(3118; 0) + 3793: mip = not found yet = 2.000244200e+00(3798; 0) + 4370: mip = not found yet = 2.000244200e+00(4375; 0)
Bug#490288: [Pkg-scicomp-devel] Bug#490288: glpk: Fails on assertion
It seems that the behaviour of glpsol and the mip solver depend on the computer architecture Yes, because glpk uses inexact (floating-point) arithmetic. and that the program doesn't always catch overflows or underflows. Most probably the failure is caused by excessive round-off errors, not by ufl/ofl. The modified example suggested by Andrew results in another failed assertion Assertion failed: ipp != ipp Error detected in file glpipp02.c at line 801 even in cases where the program without --cuts succeeds. Glpk mip solver is not sufficiently robust. However, as I said in my previous post, these mip instances are badly formulated: integer variables have large upper bounds and relatively large constraint coefficients that may cause numeric difficulties not only with glpk. I do not know how to reformulate your models. But, for example, replacing integer variables by binary ones (option --binarize) signficantly simplifies solution of your model with --cuts option as well as without it. $ glpsol -m f.mod --binarize -o f.sol Reading model section from f.mod... 5 lines were read Generating objective... Generating constraint... Model has been successfully generated ipp_basic_tech: 1 row(s) and 0 column(s) removed ipp_reduce_bnds: 4689 pass(es) made, 4688 bound(s) reduced ipp_basic_tech: 0 row(s) and 0 column(s) removed ipp_binarize: 2 integer variable(s) replaced by 14 binary ones ipp_reduce_coef: 4 pass(es) made, 6 coefficient(s) reduced lpx_intopt: presolved MIP has 3 rows, 14 columns, 28 non-zeros lpx_intopt: 14 integer columns, all of which are binary lpx_adv_basis: size of triangular part = 3 Solving LP relaxation... 0: objval = 4.688976667e+03 infeas = 1.0e+00 (0) 1: objval = 4.689023324e+03 infeas = 0.0e+00 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... + 1: mip = not found yet = -inf(1; 0) +33:4.80100e+03 = 4.785003332e+03 0.3% (8; 48) +35: mip = 4.80100e+03 = tree is empty 0.0% (0; 71) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.3 secs Memory used: 0.1 Mb (148839 bytes) $ glpsol -m f.mod --binarize --cuts -o f.sol Reading model section from f.mod... 5 lines were read Generating objective... Generating constraint... Model has been successfully generated ipp_basic_tech: 1 row(s) and 0 column(s) removed ipp_reduce_bnds: 4689 pass(es) made, 4688 bound(s) reduced ipp_basic_tech: 0 row(s) and 0 column(s) removed ipp_binarize: 2 integer variable(s) replaced by 14 binary ones ipp_reduce_coef: 4 pass(es) made, 6 coefficient(s) reduced lpx_intopt: presolved MIP has 3 rows, 14 columns, 28 non-zeros lpx_intopt: 14 integer columns, all of which are binary lpx_adv_basis: size of triangular part = 3 Solving LP relaxation... 0: objval = 4.688976667e+03 infeas = 1.0e+00 (0) 1: objval = 4.689023324e+03 infeas = 0.0e+00 (0) OPTIMAL SOLUTION FOUND Creating the conflict graph... The conflict graph has 2*2 vertices and 4 edges Generating cutting planes... 1: obj = 4.689023324e+03 frac = 1 cuts = 0 (0) 1: obj = 4.689023324e+03 frac = 1 cuts = 0 (0) Integer optimization begins... + 1: mip = not found yet = -inf(1; 0) Gomory's cuts enabled MIR cuts enabled +36:4.80100e+03 = 4.785003332e+03 0.3% (8; 46) +38: mip = 4.80100e+03 = tree is empty 0.0% (0; 69) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.1 secs Memory used: 0.1 Mb (151279 bytes) Thank you for your interest in glpk. Best regards, Andrew Makhorin -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Bug#490288: [Pkg-scicomp-devel] Bug#490288: glpk: Fails on assertion
package glpk tags 490288 confirmed upstream thanks * Ingo Feinerer [EMAIL PROTECTED] [2008-07-11 12:00]: Package: glpk Version: 4.11-1 Severity: normal The following linear program triggers an assertion and stops the program without a proper solution: var x1 integer; var x2 integer; minimize objective : x1 + x2; s.t. constraint : (8^4 - 1) * x1 - 8^4 * x2 = 0; s.t. x1NotNegative : x1 = 1; s.t. x2NotNegative : x2 = 1; end; Output of above program: [EMAIL PROTECTED]:~$ glpsol -m bug.mod -o bug.sol Reading model section from bug.mod... 11 lines were read Generating objective... Generating constraint... Generating x1NotNegative... Generating x2NotNegative... Model has been successfully generated lpx_simplex: original LP has 4 rows, 2 columns, 6 non-zeros Objective value = 2.0002442 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... Objective function is integral + 0: mip = not found yet = -inf(1; 0) + 6922: mip = not found yet = 3.0e+00(6924; 0) Assertion failed: x = lb; file glpmip2.c; line 230 I confirm the problem with glpk 4.29, which has just been uploaded to unstable. The error message is slightly different: Reading model section from bug.mod... 11 lines were read Generating objective... Generating constraint... Generating x1NotNegative... Generating x2NotNegative... Model has been successfully generated glp_simplex: original LP has 4 rows, 2 columns, 6 non-zeros Objective value = 2.0002442 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... + 0: mip = not found yet = -inf(1; 0) Assertion failed: x = lb Error detected in file glpios03.c at line 257 Aborted I am therefore forwarding this bug report to the upstream author. Andrew: could you please look at this? Please, respect the Reply-To when replying to this message. Thanks, -- Rafael -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Bug#490288: [Pkg-scicomp-devel] Bug#490288: glpk: Fails on assertion
Saturday, July 12, 2008, 12:35:26 PM, you wrote: package glpk tags 490288 confirmed upstream thanks * Ingo Feinerer [EMAIL PROTECTED] [2008-07-11 12:00]: Package: glpk Version: 4.11-1 Severity: normal The following linear program triggers an assertion and stops the program without a proper solution: var x1 integer; var x2 integer; minimize objective : x1 + x2; s.t. constraint : (8^4 - 1) * x1 - 8^4 * x2 = 0; s.t. x1NotNegative : x1 = 1; s.t. x2NotNegative : x2 = 1; end; Output of above program: [EMAIL PROTECTED]:~$ glpsol -m bug.mod -o bug.sol Reading model section from bug.mod... 11 lines were read Generating objective... Generating constraint... Generating x1NotNegative... Generating x2NotNegative... Model has been successfully generated lpx_simplex: original LP has 4 rows, 2 columns, 6 non-zeros Objective value = 2.0002442 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... Objective function is integral + 0: mip = not found yet = -inf(1; 0) + 6922: mip = not found yet = 3.0e+00(6924; 0) Assertion failed: x = lb; file glpmip2.c; line 230 I confirm the problem with glpk 4.29, which has just been uploaded to unstable. The error message is slightly different: Reading model section from bug.mod... 11 lines were read Generating objective... Generating constraint... Generating x1NotNegative... Generating x2NotNegative... Model has been successfully generated glp_simplex: original LP has 4 rows, 2 columns, 6 non-zeros Objective value = 2.0002442 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... + 0: mip = not found yet = -inf(1; 0) Assertion failed: x = lb Error detected in file glpios03.c at line 257 Aborted I am therefore forwarding this bug report to the upstream author. Andrew: could you please look at this? Please, respect the Reply-To when replying to this message. Thanks, Thank you for the bug report. The failure appears due to insufficient robustness of the glpk mip solver. It is mainly caused by unbounded integer variables (x1 and x2 have no upper bound) having relatively large coefficients in the constraint that leads to excessive round-off errors on solving LP relaxation. Unfortunately, I cannot reproduce the failure on my machine: $ glpsol -m bug.mod Reading model section from bug.mod... 11 lines were read Generating objective... Generating constraint... Generating x1NotNegative... Generating x2NotNegative... Model has been successfully generated glp_simplex: original LP has 4 rows, 2 columns, 6 non-zeros Objective value = 2.0002442 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... + 0: mip = not found yet = -inf(1; 0) + 2237: mip = not found yet = 2.000244200e+00(2242; 0) + 3113: mip = not found yet = 2.000244200e+00(3118; 0) + 3793: mip = not found yet = 2.000244200e+00(3798; 0) + 4370: mip = not found yet = 2.000244200e+00(4375; 0) . . . . . . . I need to say that using unbounded integer variables is not a good idea, because this may cause other troubles. Simple reformulation might be introducing upper bounds for x1 and x2, say, as follows: var x1 integer, = 1, = 1; var x2 integer, = 1, = 1; minimize objective : x1 + x2; s.t. constraint : (8^4 - 1) * x1 - 8^4 * x2 = 0; /* s.t. x1NotNegative : x1 = 1; */ /* s.t. x2NotNegative : x2 = 1; */ end; in which case glpsol with --cuts option is able to solve the problem to optimality on the root level: $ glpsol -m bug1.mod --cuts -o bug1.sol Reading model section from bug1.mod... 11 lines were read Generating objective... Generating constraint... Model has been successfully generated ipp_basic_tech: 1 row(s) and 0 column(s) removed ipp_reduce_bnds: 7869 pass(es) made, 7868 bound(s) reduced ipp_basic_tech: 0 row(s) and 0 column(s) removed ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced lpx_intopt: presolved MIP has 1 row, 2 columns, 2 non-zeros lpx_intopt: 2 integer columns, none of which are binary lpx_adv_basis: size of triangular part = 1 Solving LP relaxation... 0: objval = 7.868960684e+03 infeas = 1.0e+00 (0) 1: objval = 7.869039307e+03 infeas = 0.0e+00 (0) OPTIMAL SOLUTION FOUND Creating the conflict graph... The conflict graph is either empty or too big Generating cutting planes... 1: obj = 7.869039307e+03 frac = 1 cuts = 0 (0) 1: obj = 7.869039307e+03 frac = 1 cuts = 0 (0) Integer optimization begins... + 1: mip = not found yet = -inf(1; 0) Gomory's cuts enabled MIR cuts enabled + 2:8.19100e+03 = 8.19100e+03 0.0% (1; 0) + 2: mip = 8.19100e+03 = tree is empty 0.0% (0; 1) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.4 secs Memory used: 0.1 Mb (135466 bytes) Problem:
Bug#490288: [Pkg-scicomp-devel] Bug#490288: glpk: Fails on assertion
* Andrew Makhorin [EMAIL PROTECTED] [2008-07-12 16:06]: The failure appears due to insufficient robustness of the glpk mip solver. It is mainly caused by unbounded integer variables (x1 and x2 have no upper bound) having relatively large coefficients in the constraint that leads to excessive round-off errors on solving LP relaxation. [sinp] Nevertheless, in both cases the problem is badly formulated. Many reseachers do not recommend to use upper bounds of integer variables which exceed 100. Does this mean that the problem is in the formulation of that specific example or is it a bug in GLPK? If the later is the case, are you planning to fix it? -- Rafael -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Bug#490288: [Pkg-scicomp-devel] Bug#490288: glpk: Fails on assertion
Saturday, July 12, 2008, 5:56:31 PM, you wrote: * Andrew Makhorin [EMAIL PROTECTED] [2008-07-12 16:06]: The failure appears due to insufficient robustness of the glpk mip solver. It is mainly caused by unbounded integer variables (x1 and x2 have no upper bound) having relatively large coefficients in the constraint that leads to excessive round-off errors on solving LP relaxation. [sinp] Nevertheless, in both cases the problem is badly formulated. Many reseachers do not recommend to use upper bounds of integer variables which exceed 100. Does this mean that the problem is in the formulation of that specific example or is it a bug in GLPK? If the later is the case, are you planning to fix it? It is a bug in the sense that the mip solver should return GLP_EFAIL rather than cause abnormal termination. The bug will be fixed in a next version of the package. Andrew Makhorin -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Bug#490288: [Pkg-scicomp-devel] Bug#490288: glpk: Fails on assertion
* Andrew Makhorin [EMAIL PROTECTED] [2008-07-12 18:06]: Saturday, July 12, 2008, 5:56:31 PM, you wrote: Does this mean that the problem is in the formulation of that specific example or is it a bug in GLPK? If the later is the case, are you planning to fix it? It is a bug in the sense that the mip solver should return GLP_EFAIL rather than cause abnormal termination. The bug will be fixed in a next version of the package. Thanks! -- Rafael -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Bug#490288: glpk: Fails on assertion
Package: glpk Version: 4.11-1 Severity: normal The following linear program triggers an assertion and stops the program without a proper solution: var x1 integer; var x2 integer; minimize objective : x1 + x2; s.t. constraint : (8^4 - 1) * x1 - 8^4 * x2 = 0; s.t. x1NotNegative : x1 = 1; s.t. x2NotNegative : x2 = 1; end; Output of above program: [EMAIL PROTECTED]:~$ glpsol -m bug.mod -o bug.sol Reading model section from bug.mod... 11 lines were read Generating objective... Generating constraint... Generating x1NotNegative... Generating x2NotNegative... Model has been successfully generated lpx_simplex: original LP has 4 rows, 2 columns, 6 non-zeros Objective value = 2.0002442 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... Objective function is integral + 0: mip = not found yet = -inf(1; 0) + 6922: mip = not found yet = 3.0e+00(6924; 0) Assertion failed: x = lb; file glpmip2.c; line 230 Note that no bug.sol is created. -- System Information: Debian Release: 4.0 APT prefers stable APT policy: (500, 'stable') Architecture: i386 (i686) Shell: /bin/sh linked to /bin/bash Kernel: Linux 2.6.18-6-686 Locale: LANG=en_US.UTF-8, LC_CTYPE=en_US.UTF-8 (charmap=UTF-8) Versions of packages glpk depends on: ii libc6 2.3.6.ds1-13etch5 GNU C Library: Shared libraries glpk recommends no packages. -- no debconf information -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
