Re: [Bug-glpk] glpk 4.11 failed assertion

[Andrew Makhorin]

> I'm having a problem with a failed assertion in glpk 4.11.
> 
> I'm using the library interface and after setting up the problem and
> calling
> 
> lpx_adv_basis(lp);
> 
> I do
> 
> lpx_simplex(lp);
> 
> and for one particular problem, I get
> 
> Assertion failed: spx->p != 0; file glpspx2.c; line 668
> 
> When I write out the problem (attached), however, and run gplsol
> on it, I get
> 
> lpx_read_freemps: reading problem data from `/tmp/lp.mps'...
> lpx_read_freemps: problem name not specified
> lpx_read_freemps: 43 rows, 12 columns, 198 non-zeros
> lpx_read_freemps: 193 records were read
> lpx_simplex: original LP has 43 rows, 12 columns, 198 non-zeros
> lpx_simplex: presolved LP has 38 rows, 12 columns, 192 non-zeros
> lpx_adv_basis: size of triangular part = 38
>       0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (0)
>       8:   objval =   0.000000000e+00   infeas =   1.526958211e-02 (0)
> PROBLEM HAS NO FEASIBLE SOLUTION
> lpx_simplex: cannot recover undefined or non-optimal solution
> Time used:   0.0 secs
> Memory used: 0.1M (106164 bytes)
> 
> Now, I was expecting a solution, but I assume it got lost
> because I have to convert the coefficients of the problem
> to doubles as it appears that glpk doesn't support arbitrary
> precision integer arithmetic.
> 
> Still, getting an unexpected answer would be nicer than a failed
> assertion.
> 
> I can reproduce the problem by running the polyhedron_sample
> program from the latest git version of my barvinok library
> (http://www.liacs.nl/~sverdool/gitweb.cgi?p=barvinok.git;a=summary)
> with the following input:
> 18 8
>    1    0    0    0    0    0    1  -28 
>    1   16   13    0 -297    0  -99 -128 
>    1    0    0    1    0    0    0  -33 
>    1    5    0    0   18    0    6    7 
>    1   12    0    0   45    0   12   19 
>    1   17    0    0   63   -3   21   27 
>    1    6    0    0   20    0    9   16 
>    1  -24  -18    0  405    0  135  158 
>    1  -29    0    5 -108    0  -36  -41 
>    1    0    0    0    0    1    0  -28 
>    1    0    0    0    1    0    0  -36 
>    1 -102  -56    0 1161    0  387  497 
>    1  -51    0    0 -189    9  -63  -73 
>    1   -6    0    0  -20    0   -9  -10 
>    1   29    0   -5  108    0   36   45 
>    1   -8    0    0  -27    0   -9  -92 
>    1    7   -7    0  216    0   72   99 
>    1  -60    0    0 -225    0  -60  -92 
> 
> Unfortunately, as decribed above, the error disappears
> after dumping and rereading the problem.

The error appears due to huge constraint coefficients. You can call
lpx_scale_prob to scale the problem (as glpsol does).

To obtain the solution with glpsol you need to disable the lp presolver
(--nopresol), because it cannot recover non-optimal solutions.


Andrew Makhorin