Re: [Help-glpk] basis matrix is singular, but not in the saved model

[Andrew Makhorin]

> I am using GLPK to solve some game-theory problems with dense matrices
> (as I have asked about before.)  Andrew's suggestion to use column
> generation has been very useful (thank you!)

> In my current program I got the following error while running
> lpx_simplex on the main LP model:

> * 44250:   objval =   1.482023718e+00   infeas =   9.060097142e-14 (0)
> * 44300:   objval =   1.481789163e+00   infeas =   9.819968853e-16 (0)
> * 44350:   objval =   1.481729328e+00   infeas =   6.997407302e-14 (0)
> spx_invert: the basis matrix is singular
> spx_simplex: numerical problems with basis matrix
> spx_simplex: sorry, basis recovery procedure not implemented yet

> However, when I run the saved model through glpsol it arrives at a
> solution:

> lpx_read_cpxlp: reading problem data from `test.cplex'...
> lpx_read_cpxlp: 1687 rows, 2248 columns, 1898434 non-zeros
> lpx_read_cpxlp: 949119 lines were read
> lpx_write_mps: writing problem data to `test.mps'...
> lpx_simplex: original LP has 1687 rows, 2248 columns, 1898434 non-zeros
> lpx_simplex: presolved LP has 1687 rows, 2248 columns, 1898434 non-zeros
> lpx_adv_basis: size of triangular part = 1687
>       0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (0)
>     200:   objval =   1.344510660e+00   infeas =   3.297820208e-01 (0)
>     400:   objval =   1.881226167e+00   infeas =   1.941659565e-01 (0)
> ...
> *  2400:   objval =   1.481966312e+00   infeas =   7.559774601e-14 (0)
> *  2600:   objval =   1.481709975e+00   infeas =   0.000000000e+00 (0)
> *  2648:   objval =   1.481704489e+00   infeas =   2.057120297e-17 (0)
> OPTIMAL SOLUTION FOUND

> Right now my loop works something like this:

> 1. Save the model to file
> 2. Solve restricted problem with lpx_simplex
> 3. Look for additional rows (first-player strategies that improve his
> score).  If found, add them to the model and go back to step #1.
> 4. Look for additional columns (second-player strategies) with
> negative reduced cost.  If found, add them to the model and repeat
> step #1.

> Should I reset the basis before running the simplex method again?
> Could I recover from this error by resetting the basis and rerunning
> lpx_simplex?

Yes. However, before resetting the basis you could call the routine
lpx_warm_up to recompute the basis factorization and make sure that
the current basis matrix is really singular.

As another remedy you could change the basis factorization type
before the first call to lpx_simplex as follows:

   glp_set_int_parm(lp, LPX_K_BFTYPE, 3);

This feature is available in glpk 4.17, and it allows the simplex
solver using a slower, but numerically more stable version of the
basis update procedure.

I hope to implement the basis recovering procedure in the next version
of the package.