[Coin-lpsolver] basisIsAvailable()

[Matthew Saltzman]

On Thu, 10 Nov 2005, Francois Margot wrote:

>
>
> On Thu, 10 Nov 2005, Matthew Saltzman wrote:
>
>> On Wed, 9 Nov 2005, Francois Margot wrote:
>>> 
>>> I must add that the Doxygen doc of OsiSolverInterface could be improved (I 
>>> know, I can do it myself; except that to figure out what is supposed to
>>> be returned by isProvenOptimal() you have to look at solver 
>>> implementations
>>> and they are not consistent with each other ...). The current doc on
>>> isProvenOptimal() is the terse:
>>> 
>>>   Is optimality proven?
>> 
>> Of course, what that means is algorithm dependent.
>> 
>
> Well, this is exactly what I don't like. The purpose of Osi, I thought, is to 
> have an interface that is solver independent. To obtain that,
> Osi has to impose return codes that are solver independent, and have
> enough documentation so that people implementing a solver interface know 
> exactly what is required.

In the early days of OSI design, much care was taken to avoid using the 
term "solver independent".  Instead, "solver agnostic" was adopted to 
imply that, while the API was the same, the interface would "adapt" in 
certain ways to the behavior of the underlying solver.  That choice made 
development of SIs simpler, but has proved problematic in just the ways 
one would have predicted.

I don't think the choice was entirely unjustifiable.  The driving idea was 
the "principle of least surprise", but the question was, who's surprise is 
to be minimized?  A CPLEX user migrating to OsiCpxSolverInterface would be 
least surprised by solver-agnostic behavior, but an OSI user migrating 
from CPLEX to CLP or vice versa would be least surprised by 
solver-independent behavior.

One example was that, because we called the underlying solver's MPS reader 
(simplifying development), you couldn't guarantee that you were solving 
the same problem when you switched underlying solvers.  You could, however 
guarantee that the problem read into CPLEX and the problem read into 
OsiCpxSolverInterface would be the same. The result was John's readMPS(), 
a retrofit to make sure that we had a consistent way to get the same 
problem into any solver in the same way.

Another example is the kind of thing we are discussing here.

For the next version, we've largely abandonded solver agnosticism as a 
design principle.

>
> For example my impression is that IsProvenOptimal() is supposed to
> return "true" if and only if the current solution that can be obtained
> through getColSolution() is optimal for the model currently stored
> in the solver. This is fairly obvious if you are merely loading
> a LP, solve it, and access the solution. What is unclear is what happens when 
> you start modifying the model (changing bounds on variables,
> for example). This should not be left to the implementer of the solver 
> interface. For example, it would not be completely insane that
> IsProvenOptimal() returns the status of the last call to resolve() or
> initialSolve() (in fact, I believed it was so until yesterday ...), 
> independently of later modifications.
>
> The same is true for the methods getBInvRow() and others. The choice I made
> when writing the OsiCpxSolverInterface::getBInvRow() method is to make
> changes to the native Cplex function getBInvRow() method so that both
> OsiClp and OsiCpx return identical results, making Cplex behave like Clp.
> However, the behavior of Clp is not really defined anywhere in the doc I 
> could
> find. Here, the problem is the way solvers add slack variables to the 
> original
> tableau. There should be an Osi description of the way slacks are supposed
> to be handled in the original tableau, for all simplex based Osi solvers.
>
> Francois
>
>
>
>

-- 
 		Matthew Saltzman

Clemson University Math Sciences
mjs AT clemson DOT edu
http://www.math.clemson.edu/~mjs