[Coin-discuss] OSI clarifications
Lou Hafer
lou at cs.sfu.ca
Tue Jan 29 12:18:53 EST 2002
Folks,
I'd like to vote for mathematical accuracy here, on principle, and
because I think it might be important as the LP solvers are buried in branch-
cut-price codes which are trying to determine the proper action to take.
There is a price, but I think we should consider it.
I'm guessing many LP solvers --- certainly dylp --- return when they
prove any termination condition. So, a solver may well know the problem is
primal infeasible, but not necessarily take the time to decide whether it has
dual infeasibility or unboundedness. In simplex-class solvers, there is often
an asymmetry between primal and dual, so that the dual has no `phase I',
hence the problem of distinguishing primal infeasibility or unboundedness
given dual infeasibility simply does not arise. Bottom line is that it may
require a nontrivial calculation to answer isProvenDualInfeasible or
isProvenDualUnbounded when the termination condition is
isProvenPrimalInfeasible. This is the case in dylp; in other solvers it may
well go the other way.
The existing dylp OSI layer reflects the current behaviour of dylp,
which generates a return code in terms of the primal problem. This means that
proven dual unboundedness is considered to be equivalent to primal
infeasibility (accurate) and proven primal infeasibility is considered to be
equivalent to dual unboundedness (sloppy). Erling, this is relatively typical
for simplex-class solvers. From your side, I take it that proof of dual
infeasibility is more likely?
Two possible solutions (perhaps in combination):
* Change the set of isProven* functions to a single function that returns a
bit vector, one bit for each of [primal, dual] [infeas, unbounded].
Testing for any condition is then a matter of a boolean operation on the
vector. A 1 indicates the solver has proven the condition.
* Change the interface to the isProven* functions to have a default
parameter (forceCheck) that is false by default. isProven* would return
whatever the solver gives by default. Calling isProven* with forceCheck =
true would result in taking whatever action is needed to attempt to prove
the condition.
I used Brady's interpretation of isAbandoned in the dylp OSI layer.
isAbandoned will be true if dylp gives up any of a number of reasons; loss of
numerical accuracy is only one of them.
As an aside, the meaning of is*ObjectiveLimitReached is clear, but
the functions are not really implementable for dylp. Because it adds and
purges constraints and variables as it work, the objective does not change
monotonically.
Lou
More information about the Coin-discuss
mailing list