[Coin-discuss] OsiGlpk Not Correctly Reporting Infeasibility

[Brady Hunsaker]

Joseph,

Matt indicated that he was emailing you information on accessing the
repository to commit changes.  Have you received this?

Ideally, the unit test would be run before commiting new changes, but in
practice the unit test often has its own issues unrelated to any changes
you make in OsiGlpk.  So, at least run your own tests of the changed
code, and also do at least a simple test of reading an MPS file and
solving it to make sure that still works.

Other than that, feel free to make changes.  The history of OsiGlpk is
that Vivian de Smedt and I wrote (separately) most of the original code.
  A lot of that was based on OsiCpx, I think. I have been maintaining it
since then, often based on contributed changes like the ones you did
previously.  So I should be able to answer questions about why things
were done a certain way, though the answer may sometimes be "that's how
OsiCpx" or "no particular reason".  In general, don't be afraid to make
changes.

Brady


Joseph Young wrote:
> Hi,
> 	Currently, OsiGlpk does not always correctly report if a problem 
> is infeasible.  Specifically, if GLPK can determine that the problem is 
> infeasible during preprocessing, this information is lost.
> 
> 	During initialSolve(), the preprocessor is turned on.  This 
> changes what error codes lpx_simplex() will return.  Two such error codes 
> that may be returned are LPX_E_NOPFS and LPX_E_NODFS which mean primal and 
> dual infeasibility respectively.  These error codes must be trapped, or 
> the information that this problem is primal or dual feasible will be lost.
> 
> 	According the documentation in GLPK:
> 
> Note that the presolver is able to recover only optimal solutions. If a 
> computed solution is infeasible or non-optimal, the corresponding solution 
> of the original problem cannot be recovered and therefore remains 
> undefined. If the user needs to know a basic solution even if it is 
> infeasible or non-optimal, the presolver must be disabled.
> 
> This means that subsequent calls to isProvenPrimalInfeasible() and 
> isProvenDualInfeasible() within OSI will return false even when the 
> problem is primal or dual infeasible.  This happens because 
> lpx_get_status(),lpx_get_prim_stat(), lpx_get_dual_stat() will return 
> LPX_UNDEF, LPX_P_UNDEF, and LPX_D_UNDEF respectively when the problem is 
> determined to be infeasible during preprocessing.
> 
> 	In order to fix this, the error codes from lpx_simplex() must be 
> trapped and a flag set within OsiGlpk.  Then, this flag must be checked 
> within the routines isProvenPrimalInfeasible() and 
> isProvenDualInfeasible().  This is a little bit tricky since there are 
> several places within the code where the flag needs to be reset (such as 
> when the problem is modified.)
> 
> Sinc, Joseph Young
> 
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss


-- 
Brady Hunsaker
Assistant Professor
Industrial Engineering
University of Pittsburgh
http://www.engr.pitt.edu/hunsaker/