[Coin-discuss] Principles for maintaing solutions in a solver interface.

[Matthew Saltzman]

On Wed, 30 Apr 2003, Lou Hafer wrote:

> Folks,
>
> 	I've been trying to work out some underlying principles for the
> behaviour of a solver interface (SI) with respect to the pre-solver solution,
> and I'm left with some puzzles. Here's a sampling.
>
>
>   * unitTest clearly expects a SI to generate an initial solution when it reads
>     a problem from an MPS file --- it tests for this directly. It's easy enough
>     to extend this to loadProblem. Both are batch activities.
>
>     But what about when the client is incrementally building a system using
>     addCol/addRow? Should the SI incrementally maintain a valid pre-solver
>     solution? It's possible, but some work would be required to do it
>     efficiently.

I'll need to go back to the code to see what this is about.  Soon as I'm
done grading exams...  Comments below are from memory right now.

I don't find the idea of making the SI work hard to do this very
appealing.

>
>   * Does a SI possess exactly one solution, or is there a notion of `the
>     solution provided by the client' vs. `the solution provided by the
>     solver'? If there are conceptually two solutions, which takes precedence?
>     The chronologically most recent?

I know there is at most one solution.  IIRC, if the solver has one, that's
the one that's used.

>
>   * If I have a solution from the solver, and the client incrementally
>     modifies the problem, what are the rules? Should the solver attempt to
>     incrementally maintain a solution? Or is it invalid until the next time a
>     complete solution is provided (either by the client or the solver)?

I think the solution is invalid.  In the XPRESS and CPLEX SI classes,
modifying the problem invalidates most of the cache (including solutions).
In the next-gen SI base class, I intended that modifying the problem would
invalidate anything in the cache that could no longer either be relied on
to be correct or updated in place more efficiently than it could be
refreshed.

I don't think the SI should be attempting to maintain solutions
dynamically.  That's something that the underlying solver can do better
than we can.  The principle I'm applying is a sort of "lazy evaluation"
idea.  Like, "Don't refresh the cache until the value is requested."  For
real work done by the solver, I think the user should explicitly ask for
the work to be done, i.e., if you ask for a solution and it's invalid, you
need to either set it or call solve() or resolve() (usually the latter).

>
>   * If the SI has a valid solution (from client or solver), and a call to the
>     solver fails, is the existing solution invalidated?

It should be, until solve() or resolve() is called or a solution is
explicitly loaded.

>
> 	If I were to make a proposal, for maintenance of solutions in general,
> it would be something like this:
>
>   * The SI possesses a single, unique solution.

Yes.

>
>   * The SI will implement a method, inventSolution, that generates a
>     `reasonable' initial solution appropriate for the solver. Definition of
>     reasonable to be determined.

I think I want to argue about this, but I'll need to do it later when I
can spend a little time with the code.

>
>   * When a problem is loaded, either in batch or incrementally, no solution
>     exists until the client calls inventSolution or initialSolve.

Yes (subject to the resolution of "inventSolution()").

>
>   * Modifications to the problem invalidate the existing solution until the
>     next call to inventSolution, initialSolve, or resolve.

Yes (as above).

>
>   * A failed call to the solver invalidates any existing solution.

Yes.

>
>   * Solutions may be imposed on the SI by the client (setColSolution,
>     setRowSolution) but the SI is under no obligation to attempt to impose
>     them on the solver.

Yes.  This is what we agreed in the early discussions.  If the solver
could accept them, then they should be passed in, but if not, no
extraordinary steps should be taken.

>
> Admittedly, there's a bias here toward ease of SI implementation.

Yes, exactly.

>
> Matt, you mentioned `the original spec'. Is it still relevant? Is there a copy
> around somewhere?

<Removes foot from mouth> "The original spec" was probably not a formal
document.  If it was, I don't have a copy.  The XPRESS interface was
"speced" to the existing SI and OslSI classes, and questions like this one
were resolved in discussions with JP, Laci, and others.  AFAIK Tobias
wrote the CPLEX interface using the same strategy.  So the code *is* the
spec in some sense (depending on the what the meaning of "is" is).  (If
I'm missing something, I hope JP will correct me...)

>
> 							Lou

-- 
		Matthew Saltzman

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