Re: [Help-glpk] Error: unable to factorize the basis matrix

[Andrew Makhorin]

On Thu, 2013-08-29 at 17:41 +0100, Cherif Mouaouia Bouzid wrote:
> Hello 
> 
> 
> Thank you for what you are doing. 
> 
> 
> I have a recurrent problem when solving mixed-integer LPs.
> 
> 
> Attached are an LP file example and its corresponding Output file. 
> 
> Here is the glpsol's terminal output:
> 
> GLPSOL: GLPK LP/MIP Solver, v4.45
> Parameter(s) specified in the command line:
>  --lp example.lp --output example.out
> Reading problem data from `example.lp'...
> example.lp:1282: warning: missing final end of line
> 952 rows, 634 columns, 2536 non-zeros
> 317 integer variables, all of which are binary
> 1282 lines were read
> GLPK Integer Optimizer, v4.45
> 952 rows, 634 columns, 2536 non-zeros
> 317 integer variables, all of which are binary
> Preprocessing...
> 952 rows, 634 columns, 2536 non-zeros
> 317 integer variables, all of which are binary
> Scaling...
>  A: min|aij| =  1.000e+00  max|aij| =  4.134e+04  ratio =  4.134e+04
> GM: min|aij| =  1.655e-01  max|aij| =  6.043e+00  ratio =  3.652e+01
> EQ: min|aij| =  2.738e-02  max|aij| =  1.000e+00  ratio =  3.652e+01
> 2N: min|aij| =  3.027e-02  max|aij| =  1.262e+00  ratio =  4.167e+01
> Constructing initial basis...
> Size of triangular part = 952
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.45
> 952 rows, 634 columns, 2536 non-zeros
>       0: obj =   6.675300000e+03  infeas =  2.794e+02 (0)
>     500: obj =   9.252882224e+03  infeas =  1.295e+02 (0)
> Error: unable to factorize the basis matrix (2)
> Sorry, basis recovery procedure not implemented yet
> glp_intopt: cannot solve LP relaxation
> Time used:   0.0 secs
> Memory used: 1.0 Mb (1026045 bytes)
> Writing MIP solution to `example.out'...
> 
> 
> 
> I'm using Ubuntu 12.04.
> 
> Regards
> 
> 
> -- 
> 
> Cherif, Algeria
> 

Please use the most recent version of glpk, which is 4.52; see
http://ftp.gnu.org/gnu/glpk/ . There have been made some essential
improvements in the basis factorization routines, and now glpsol solves
your mip successfully:

GLPSOL: GLPK LP/MIP Solver, v4.52
Parameter(s) specified in the command line:
 --lp example.lp --log example.log
Reading problem data from 'example.lp'...
example.lp:1282: warning: missing final end of line
952 rows, 634 columns, 2536 non-zeros
317 integer variables, all of which are binary
1282 lines were read
GLPK Integer Optimizer, v4.53
952 rows, 634 columns, 2536 non-zeros
317 integer variables, all of which are binary
Preprocessing...
952 rows, 634 columns, 2536 non-zeros
317 integer variables, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  4.134e+04  ratio =  4.134e+04
GM: min|aij| =  1.655e-01  max|aij| =  6.043e+00  ratio =  3.652e+01
EQ: min|aij| =  2.738e-02  max|aij| =  1.000e+00  ratio =  3.652e+01
2N: min|aij| =  1.514e-02  max|aij| =  1.240e+00  ratio =  8.194e+01
Constructing initial basis...
Size of triangular part is 952
Solving LP relaxation...
GLPK Simplex Optimizer, v4.53
952 rows, 634 columns, 2536 non-zeros
      0: obj =   6.675300000e+03  infeas =  1.388e+02 (0)
    500: obj =   8.180770197e+03  infeas =  7.211e+01 (0)
*   634: obj =   1.185575775e+04  infeas =  0.000e+00 (0)
*   957: obj =   7.589768643e+02  infeas =  0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
+   957: mip =     not found yet >=              -inf        (1; 0)
+  1291: mip =     not found yet >=   1.314220420e+03        (273; 0)
+  1371: >>>>>   8.712560000e+03 >=   1.314220420e+03  84.9% (301; 0)
+  1482: >>>>>   4.443280000e+03 >=   1.358039358e+03  69.4% (304; 6)
+  1511: >>>>>   2.317350000e+03 >=   1.444905676e+03  37.6% (158; 164)
+  1511: mip =   2.317350000e+03 >=     tree is empty   0.0% (0; 619)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   7.2 secs
Memory used: 1.5 Mb (1615938 bytes)