[Top][All Lists]
[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