[Coin-discuss] OSI clarifications

[Brady Hunsaker]

On Tue, Jan 29, 2002 at 05:27:49PM +0100, Erling D. Andersen wrote:

> 
> >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.
> 
> I think the reverse is the case. Usually people say their problem is 
> unbounded meaning it is dual infeasible.
> 
> Note some interior-point methods actually detect dual infeasibility 
> but not unboundedness. This is the case for MOSEK (not linked to
> COIN yet).
> 

I had only considered solvers that are simplex-based, which was a
mistake.  There are four cases for primal and dual feasibility, and
perhaps we need to explicitly address them all:

1. Primal and dual feasible = optimal
2. Primal feasible, dual infeasible = primal unbounded (this is iff)
3. Primal infeasible, dual feasible = dual unbounded (again, iff)
4. Primal and dual infeasible

Some applications may instead be concerned with primal feasibility or
dual feasibility without regard to the other.  Should we offer six
functions?  They could be as follows:

A. isProvenOptimal
B. isProvenPrimalUnbounded
C. isProvenDualUnbounded
D. isProvenPrimalDualInfeasible

E. isProvenPrimalInfeasible
F. isProvenDualInfeasible

Of course we only strictly need one set or the other, but it may be
advantageous to have all six.  For example, simplex-based solvers can
probably easily give information about A, B, and E.  Determining C, D,
and F would be harder, but most (simplex-based) applications probably
care about A, B, and/or E, so the expensive calculations to determine
C,D,F would be avoided.  

I apologize for making things more complicated.  I have now presented
three possibilities for dealing with the question, and I'd like to
know which (if any) other people prefer.  As a summary, the three
choices I see are:

1. Include options A,B,E by reinterpreting isProvenDualInfeasible as
   isProvenPrimalUnbounded.  I no longer like this idea since it
   apparently ignores the needs of non-simplex solvers.
2. Include options A,E,F by strictly interpreting the existing
   functions.  A disadvantage is that computing F may be expensive for
   some solvers and people using those solvers really care more about
   B.
3. Include all six options: A,B,C,D,E,F.  Interfaces would be
   encouraged to generate each as efficiently as possible in the hopes
   that the more expensive ones would not be used much.  The
   disadvantage is that we have some redundancy.

Right now I prefer the 3rd choice.

Brady