Re: [Help-glpk] the basis matrix becomes singular when resolving iteratively

[Andrew Makhorin]

> I suffer a problem when solve a LP based on a
> cutting plane method via GLPK.

> The original problem has enumerous constrains. So at each time, only
> some of them are included in�the LP. The modified problem is solved by
> GLPK. The obtained optimal value is an upper bound on the original
> optimal value (max problem). After the modified problem is solved,�a
> subproblem is solved to determine which new constrain should be added
> to improve the bound.� My programm is:

> ******************************************

> lp�=�glp_create_prob(); 
> ... // construct the initial problem by adding rows and columns
> glp_simplex(lp, smparam); // solve the initial LP
> while(1)
> {
> ����� ... // solve the subproblem which is constructed� from
> the optimal solution of modified LP
> �������if(stop)// check the stop criterion
> ����� {
> ��������
> break;
> ������
> }
> ����� // add a new
> constrain which is determined by the optimal solution of the�above 
> subproblem 
> ����� glp_add_rows(lp,1);
> ����� glp_set_row_bnds(lp,...);
> ����� glp_set_mat_row(lp,...);
> �����
> glp_simplex(lp, smparam);������ // resolve the new LP
> }
> *******************************************
> The above code is ok when running on some small�instances, by for�many
> large scale instances, error happens at the second "glp_simplex" after
> some iterations. The return value is "GLP_EFAIL ", error message is
> "the basic matrix is singular .....".�� but when I reconstruct a new
> LP using all the data from "lp" when error occurs, the new LP can be
> soved without any errors.

> so for the problem, whether some other routines should be called
> before "glp_simplex". Should the basis fractorization be computed from
> scratch each iteration? or how to utilize the previous one? why the
> above error happens?

> Any help is very appreciated.

Glp_simplex always starts from the current basis defined in the
problem object, which is either an initial basis you provided or the
basis from a previous call to glp_simplex in case of re-optimization.
If glp_simplex returns GLP_FAIL on re-optimization, but is able to
successfully solve the same lp from scratch, you can try to provide
some other basis to start from in case of failure, e.g.

. . .
ret = glp_simplex(lp, smparam); // resolve the new LP
if (ret == GLP_EFAIL)
{  glp_adv_basis(lp, 0);
   ret = glp_simplex(lp, smparam);
   . . .
}

However, it is reasonable to understand what causes the failure.
It may happen that some cutting planes you add are badly scaled due
to tiny or huge constraint coefficients at basic columns that makes
the current basis matrix ill-conditioned.