[Coin-discuss] OSI clarifications

[Brady Hunsaker]

In the process of helping Vivian de Smedt write a COIN/OSI interface to
GLPK, we've come upon several areas where we'd like to clarify the
expected behavior of the interface.  My hope is that with a little
discussion here we can make things clear, and I will gladly update the
documentation to reflect any clarifications.

Rather than present a lot of issues at once, I intend to spread these
out over time so any discussion is more focused.  To start things off,
I'm interested in the member functions that report on the solution
status.  There are seven: isAbandoned(), isProvenOptimal(),
isProvenPrimalInfeasible(), isProvenDualInfeasible(),
isIterationLimitReached(), isPrimalObjectiveLimitReached(), and
isDualObjectiveLimitReached().

The biggest grey area I see here is with isProvenPrimalInfeasible()
and isProvenDualInfeasible().  Technically, it is possible for a
problem to be both primal and dual infeasible, though this situation
is often ignored.  To be fair, I think that it is more of a
"pathological" case that rarely (if ever) occurs in real problems.
When most people say "dual infeasible", I think they really mean
"primal unbounded", since this is more of a concern.  CPLEX, for
example, tells you whether the problem is primal infeasible and primal
unbounded, but it does not easily reveal the case of primal and dual
infeasibility.

Given that, we need to decide whether isProvenDualInfeasible() really
means dual infeasible, or if we just want to interpret it as "primal
unbounded".  In the latter case, a problem that is primal and dual
infeasible would return "true" to isProvenPrimalInfeasible() and
"false" to isProvenDualInfeasible().  A better long-term solution
would be to change the name of the function, but with appropriate
documentation I think this would work fine for now.  An advantage of
this scheme is that then the problem should return "true" to exactly
one of the seven status functions.

The alternative is that we really mean "dual infeasible".  In this
case, a problem that is primal infeasible would have to be correctly
checked to see whether it is also dual infeasible (primal unbounded
problems are dual infeasible, so that case is still easy).  This would
require the current interfaces to be reexamined (the CPLEX interface,
for example, does not exhibit this behavior).

I prefer the former solution, with a long-term recommendation of
adding a new test isProvenPrimalUnbounded() and deprecating use of
isProvenDualInfeasible() (though we could still support it).  In the
short term, we could just make the interpretation clear in the
documentation.

Other status functions, such as isProvenOptimal(),
isIterationLimitReached(), isPrimalObjectiveLimitReached(), and
isDualObjectiveLimitReached(), seem clear to me. 

My understanding of isAbandoned() is that this should return "true" if
none of the others are true.  That is, we stopped the solver even
though none of the terminating conditions occurred.

If we interpret isProvenDualInfeasible() as "primal unbounded", then
we would have the expected behavior that at any time, exactly one of
the status functions will return "true".  In the case that a limit is
reached just as optimality or infeasibility is proven, I believe we
should expect the isProvenXXX function to return true and the
isXXXLimitReached function to return false, even though the limit was
just reached.

Please let me know what you think of this interpretation.  I think
it's important that we make these details clear for both developers
and programmers using the interface.  Thanks,

Brady

----------------
Brady Hunsaker
Georgia Institute of Technology
Program in Algorithms, Combinatorics, and Optimization
School of Industrial and Systems Engineering

E-mail address:   hunsaker at isye.gatech.edu