Re: [Bug-glpk] Assertion failed: ipp != ipp; ..\src\glpipp02.c at line 801

[Andrew Makhorin]

Xypron,

Thank you for your bug report.

> running glpsol --cuts on the following model gives an error

> Model has been successfully generated
> ipp_basic_tech:  5 row(s) and 0 column(s) removed
> Assertion failed: ipp != ipp
> Error detected in file ..\src\glpipp02.c at line 801

> glpsol --version
> GLPSOL: GLPK LP/MIP Solver 4.28

> Best regards

> Xypron

> param a ,integer;
> param b ,integer;
> param c ,integer;
> var x integer;
> var y integer;

> st1: a*x + b*y >= 21;
> st1a: a*x + b*y <= 33;
> st2: x >= 1;
> st3: x <= 10000;
> st4: y >= -10000;
> st5: y <= -1;
> minimize m: a *x + b * y;

> solve;

> display x, y;

> data;

> param a := 51;
> param b := 34;

> end;

Most probably the bug appears because of excessive round-off errors.
However, I cannot reproduce it on my machine:

Reading model section from untitled.mod...
Reading data section from untitled.mod...
24 lines were read
Generating st1...
Generating st1a...
Generating st2...
Generating st3...
Generating st4...
Generating st5...
Generating m...
Model has been successfully generated
glp_simplex: original LP has 7 rows, 2 columns, 10 non-zeros
glp_simplex: presolved LP has 2 rows, 2 columns, 4 non-zeros
lpx_adv_basis: size of triangular part = 2
      0:   objval =   1.700000000e+01   infeas =   1.000000000e+00 (0)
      1:   objval =   2.100000000e+01   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     1: mip =     not found yet >=              -inf        (1; 0)
+  1928: mip =     not found yet >=   2.100000000e+01        (2362; 0)
+  2790: mip =     not found yet >=   2.100000000e+01        (3224; 0)
+  3461: mip =     not found yet >=   2.100000000e+01        (3895; 0)
+  4034: mip =     not found yet >=   2.100000000e+01        (4468; 0)
. . . . .

The problem seems to be hard due to large bounds of integer variables.
However, with option '--binarize' glpsol solved the problem quickly:

Reading model section from untitled.mod...
Reading data section from untitled.mod...
24 lines were read
Generating st1...
Generating st1a...
Generating st2...
Generating st3...
Generating st4...
Generating st5...
Generating m...
Model has been successfully generated
ipp_basic_tech:  5 row(s) and 0 column(s) removed
ipp_reduce_bnds: 1962 pass(es) made, 3922 bound(s) reduced
ipp_basic_tech:  0 row(s) and 0 column(s) removed
ipp_binarize: 2 integer variable(s) replaced by 26 binary ones
ipp_reduce_coef: 3 pass(es) made, 3 coefficient(s) reduced
lpx_intopt: presolved MIP has 4 rows, 26 columns, 78 non-zeros
lpx_intopt: 26 integer columns, all of which are binary
lpx_adv_basis: size of triangular part = 4
Solving LP relaxation...
      0:   objval =  -2.398700000e+05   infeas =   1.000000000e+00 (0)
      2:   objval =   2.100000000e+01   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     2: mip =     not found yet >=              -inf        (1; 0)
+  4390: mip =     not found yet >=     tree is empty        (0; 4925)
PROBLEM HAS NO INTEGER FEASIBLE SOLUTION
Time used:   1.6 secs
Memory used: 0.4 Mb (413164 bytes)
Display statement at line 17
x = 0
y = 0
Model has been successfully processed