[Coin-discuss] problems with OSL on Red Hat [was: AAP_BP example]

[Matthew Galati]

Those problems are (most likely) cases where the search tree took a path 
that lead to a an infeasible subproblem. However, that subtree might 
still contain the optimal solution and should not have been fathomed. 
This is where the restore_feasibility should find a new column that 
breaks the certificate of infeasibility. That is, you optimize over the 
subproblem with a cost vector equal to the given ray, i.e. you are 
trying to find a column where p'A < 0 (where A is your master problem 
coefficient matrix). This assumes that the argument sent to restore 
feasibility is a valid certificate. Adding a sanity check "isProof" 
should show that the return from OsiOsl's getDualRays returns a ray that 
is not a certificate. In my check I am using the following 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

Using the (negative) of the return of OsiClp::getDualRays works fine. 
Using the current return (or its negative) of OsiOsl and OsiCpx does not 
provide a proof. Using the return of CPXdualfarkas also works fine - but 
this is not currently implemented in OsiCpx. I might be implementing 
something wrong - but that is my guess. For anyone that is interested, I 
have some test cases where the isProof(OsiOsl/Cpx::getDualRays) = false.

For the OsiOsl implementation they return ekk_rowaux. In the comments. 
however, I see *TEST*, which is often a red flag. The OSL documentation 
states: "ekk_rowaux returns a pointer to an array that contains the row 
auxiliary solve information." Maybe someone can tell me if this is 
suppose to contain a dual ray, in the case of primal infeasibility.

Matt


> 6.1 takes very long to solve and at last stops with a wrong solution of 48.
> The same seems to apply for problems 6.4, 8.2-8.4, 10.2 and 10.4. I didn't
> wait for a solution for these problems, but it seems to be the same behaviour
> as with 6.1. The problems not named are solved quite fast and correctly.
> So what are your results with the problems in question? Is there another
> problem with OSL (with getDualRays as Matthew reported)? Does this affect only
> the AAP or should I return to CLP in general (OSL was faster so far)?


-- 
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/