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.000000000e+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, <= 10000; var x2 integer, >= 1, <= 10000; 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.000000000e+00 (0) 1: objval = 7.869039307e+03 infeas = 0.000000000e+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.191000000e+03 >= 8.191000000e+03 0.0% (1; 0) + 2: mip = 8.191000000e+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: bug1 Rows: 2 Columns: 2 (2 integer, 0 binary) Non-zeros: 4 Status: INTEGER OPTIMAL Objective: objective = 8191 (MINimum) No. Row name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 1 objective 8191 2 constraint 0 0 = No. Column name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 1 x1 * 4096 1 10000 2 x2 * 4095 1 10000 Integer feasibility conditions: INT.PE: max.abs.err. = 0.00e+00 on row 0 max.rel.err. = 0.00e+00 on row 0 High quality INT.PB: max.abs.err. = 0.00e+00 on row 0 max.rel.err. = 0.00e+00 on row 0 High quality End of output Nevertheless, in both cases the problem is badly formulated. Many reseachers do not recommend to use upper bounds of integer variables which exceed 100. Andrew Makhorin -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]