[Bug-glpk] Re: [Pkg-scicomp-devel] Bug#490288: glpk: Fails on assertion

[Andrew Makhorin]

Saturday, July 12, 2008, 12:35:26 PM, you wrote:

> package glpk
> tags 490288 confirmed upstream
> thanks

> * Ingo Feinerer <address@hidden> [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:
>> 
>> address@hidden:~$ 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