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

[jipingtao]

Hello,

 

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.

 

 

Sincerely

 

T.J.

 

 

---