[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: jipingtao
Subject: [Help-glpk] the basis matrix becomes singular when resolving iteratively
Date: Tue, 17 Nov 2009 11:29:02 +0800

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
      ... // solve the subproblem which is constructed  from the optimal solution of modified LP
       if(stop)// check the stop criterion
      // add a new constrain which is determined by the optimal solution of the above subproblem
      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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]