bug-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Andrew Makhorin
Subject: [Bug-glpk] Re: [Pkg-scicomp-devel] Bug#490288: glpk: Fails on assertion
Date: Mon, 14 Jul 2008 19:03:39 +0400

> 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.000000000e+00 (0)
      1:   objval =   4.689023324e+03   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     1: mip =     not found yet >=              -inf        (1; 0)
+    33: >>>>>   4.801000000e+03 >=   4.785003332e+03   0.3% (8; 48)
+    35: mip =   4.801000000e+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.000000000e+00 (0)
      1:   objval =   4.689023324e+03   infeas =   0.000000000e+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.801000000e+03 >=   4.785003332e+03   0.3% (8; 46)
+    38: mip =   4.801000000e+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






reply via email to

[Prev in Thread] Current Thread [Next in Thread]