Re: [Bug-glpk] Assertion failed: spx->p != 0; file glpspx2.c; line 668

[Andrew Makhorin]

> Hello!
> 
> glpsol crushed on the attached input MPS-file with an internal assert.
> The complete output:
> 
> address@hidden bug]$ glpsol prob3.mps
> lpx_read_mps: reading problem data from `prob3.mps'...
> lpx_read_mps: problem elsom_lp
> lpx_read_mps: 1986 rows, 3280 columns, 9003 non-zeros
> lpx_read_mps: 28 integer columns, none of which are binary
> lpx_read_mps: 13862 cards were read
> lpx_simplex: original LP has 1986 rows, 3280 columns, 9003 non-zeros
> lpx_simplex: presolved LP has 1950 rows, 2814 columns, 6243 non-zeros
> lpx_adv_basis: size of triangular part = 1926
>       0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (10)
>     116:   objval =   7.646381712e+08   infeas =   3.424473137e-24 (4)
> *   116:   objval =   7.646381712e+08   infeas =   6.225692162e-20 (4)
> *   200:   objval =   6.174001496e+08   infeas =   2.313458737e-20 (0)
> *   251:   objval =   5.968232068e+08   infeas =   1.776356839e-14 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> +   251: mip =     not found yet >=              -inf        (1; 0)
> spx_simplex: numerical instability (dual simplex)
> +   629: mip =   1.235198649e+11 >=   5.968232068e+08  99.5% (16; 0)
> spx_simplex: numerical instability (dual simplex)
> spx_simplex: numerical instability (dual simplex)
> spx_simplex: numerical instability (dual simplex)
> spx_simplex: numerical instability (dual simplex)
> spx_simplex: numerical instability (dual simplex)
> spx_simplex: numerical instability (dual simplex)
> spx_simplex: numerical instability (dual simplex)
> +  3100: mip =   1.188070884e+11 >=   5.968232068e+08  99.5% (52; 11)
> +  3226: mip =   8.120514686e+10 >=   5.968232068e+08  99.3% (56; 16)
> spx_simplex: numerical instability (dual simplex)
> spx_simplex: numerical instability (primal simplex, phase I)
> spx_simplex: numerical instability (dual simplex)
> Assertion failed: spx->p != 0; file glpspx2.c; line 668
> 
> I've compiled GLPK with the following flags: "-O3 -march=pentium4
> -ffast-math" with gcc version 3.3.4 20040817 (ALT Linux, build
> 3.3.4-alt1) on pentium4 with 2Gb of RAM.

Thank you for the bug report.

Numerical instability is caused by very large objective coefficients,
i.e. the objective function is badly scaled (unfortunately, the glpk
simplex solver currently has no feature to scale the objective).

I scaled the objective manually multiplying all its coefficients by
1e-6, and this allowed me solving your instance to optimality without
any troubles (see also the solution sheet attached):

lpx_read_mps: reading problem data from `prob3.mps'...
lpx_read_mps: problem elsom_lp
lpx_read_mps: 1986 rows, 3280 columns, 9003 non-zeros
lpx_read_mps: 28 integer columns, none of which are binary
lpx_read_mps: 13862 cards were read
lpx_simplex: original LP has 1986 rows, 3280 columns, 9003 non-zeros
lpx_simplex: presolved LP has 1950 rows, 2814 columns, 6243 non-zeros
lpx_adv_basis: size of triangular part = 1926
      0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (10)
    114:   objval =   8.032480825e+02   infeas =   3.424473137e-24 (4)
*   114:   objval =   8.032480825e+02   infeas =   6.225692162e-20 (4)
*   200:   objval =   6.679232698e+02   infeas =   0.000000000e+00 (0)
*   265:   objval =   5.968232068e+02   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+   265: mip =     not found yet >=              -inf        (1; 0)
+   474: mip =     not found yet >=   5.968232068e+02        (14; 0)
+   630: mip =   1.236494649e+05 >=   5.968232068e+02  99.5% (24; 0)
+   878: mip =   1.236494649e+05 >=   5.968232068e+02  99.5% (31; 2)
+  1076: mip =   1.236494649e+05 >=   5.968232068e+02  99.5% (42; 3)
+  1377: mip =   1.236494649e+05 >=   6.616232068e+02  99.5% (50; 4)
+  1505: mip =   9.991497561e+04 >=   6.616232068e+02  99.3% (55; 5)
+  1741: mip =   9.991497561e+04 >=   7.076029582e+02  99.3% (59; 13)
+  2010: mip =   9.991497561e+04 >=   7.076029582e+02  99.3% (69; 14)
+  2247: mip =   8.599351186e+04 >=   7.076029582e+02  99.2% (70; 16)
+  2497: mip =   8.599351186e+04 >=   7.076029582e+02  99.2% (71; 40)
+  2751: mip =   8.599351186e+04 >=   7.076029582e+02  99.2% (78; 43)
+  2971: mip =   8.599351186e+04 >=   7.076029582e+02  99.2% (90; 44)
. . . . .
+ 71359: mip =   6.237783411e+04 >=   4.809589314e+04  22.9% (42; 3747)
+ 71621: mip =   6.237783411e+04 >=   4.809589314e+04  22.9% (42; 3765)
+ 71859: mip =   6.237783411e+04 >=   5.761732214e+04   7.6% (41; 3813)
+ 72182: mip =   6.237783411e+04 >=   5.761732214e+04   7.6% (40; 3823)
+ 72540: mip =   6.237783411e+04 >=   5.761732214e+04   7.6% (32; 3859)
+ 72866: mip =   6.237783411e+04 >=   5.761732214e+04   7.6% (32; 3881)
+ 73102: mip =   6.237783411e+04 >=   5.761732214e+04   7.6% (32; 3890)
+ 73278: mip =   6.237783411e+04 >=   5.761732214e+04   7.6% (23; 3939)
+ 73543: mip =   6.237783411e+04 >=   5.761732214e+04   7.6% (24; 3954)
+ 73749: mip =   6.237783411e+04 >=   5.761732214e+04   7.6% (13; 4022)
+ 73978: mip =   6.237783411e+04 >=   5.919589314e+04   5.1% (13; 4060)
+ 74271: mip =   6.237783411e+04 >=   5.919589314e+04   5.1% (13; 4075)
+ 74525: mip =   6.237783411e+04 >=   5.919589314e+04   5.1% (10; 4110)
+ 74851: mip =   6.237783411e+04 >=   5.919589314e+04   5.1% (10; 4125)
+ 75142: mip =   6.237783411e+04 >=   5.919589314e+04   5.1% (7; 4163)
+ 75327: mip =   6.237783411e+04 >=   5.919589314e+04   5.1% (9; 4174)
+ 75641: mip =   6.237783411e+04 >=   5.919589314e+04   5.1% (8; 4190)
+ 75962: mip =   6.237783411e+04 >=   5.919589314e+04   5.1% (8; 4206)
+ 76272: mip =   6.237783411e+04 >=   5.919589314e+04   5.1% (9; 4221)
+ 76477: mip =   6.237783411e+04 >=     tree is empty   0.0% (0; 4295)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   220.7 secs
Memory used: 3.7M (3932060 bytes)
lpx_print_mip: writing MIP problem solution to `sol.txt'...


Andrew Makhorin

sol.txt.bz2
Description: Binary data