[Coin-discuss] getDualRays

[Matthew Galati]

The current implementation of OsiCpxSolverInterface::getDualRays seems 
to give back incorrect rays, i.e., they do not provide a certificate. I 
have not looked carefully at why yet - perhaps someone else can let me 
know - otherwise I can try and debug.

An alternative is to use the built-in cplex call CPXdualfarkas. However, 
I noticed that there seems to be a difference in the direction of the 
dual ray as returned by different solvers. Following the CPX definition:

     p is a proof iff
 

     Let z_j = u_j where p' A_j > 0
             = l_j where p' A_j < 0
 

     p'b - p'Az > 0

the return of CPXdualfarkas does in fact provide a certificate. But, the 
return of getDualRays from CLP (call it pCLP), does not. However, -pCLP 
does. I am guessing this has to do with the solvers underlying assumptions?

This causes a problem, for example, when implementing branch and price 
in BCP, since the different solver returns are inconsistent. To get both 
CLP and CPX to work with BCP for branch and price, I changed OsiCpx's 
implementation of getDualRays to use CPXdualfarkas, but I flip the 
direction before returning. One additional problem I encountered, the 
CPXdualfarkas requests the getEnvironmentPtr() and will not compile if 
getDualRays is a const method. I made the method non-const, which, of 
course, forced me to change the base class as well. If we do switch to 
CPXdualfarkas maybe someone has a better solution.

Thanks,
Matt




-- 
Matthew Galati
ISE Lehigh University
IBM Service Parts Solutions
610.758.4042 (Office)
610.882.0779 (Home)
magh at lehigh.edu, magal11 at us.ibm.com
http://sagan.ie.lehigh.edu/mgalati/