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

Gernot Salzer salzer at logic.at
Mon Jul 14 10:41:26 UTC 2008


[ 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.801000000e+03 >=   2.000416667e+00 100.0% (2988; 0)
+  2986: mip =   4.801000000e+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 <feinerer at logic.at> [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:
> >> 
> >> feinerer at resistance:~$ 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





More information about the Pkg-scicomp-devel mailing list