[Coin-lpsolver] basisIsAvailable()

[Matthew Saltzman]

On Wed, 9 Nov 2005, Francois Margot wrote:

> On Tue, 8 Nov 2005, Matthew Saltzman wrote:
>
>> On Tue, 8 Nov 2005, John J Forrest wrote:
>> 
>>> Francois,
>>> 
>>> The description of basisIsAvailable does not say anything about an optimal
>>> basis.  I thought it was more so you can distinguish Volume algorithm.
>>> 
>>> I can add optimalBasisIsAvailable if you want but can the OsiCpx
>>> maintainer tell me what they think basisIsAvailable means?
>> 
>> I think Tobias must have written it, but the implementation of 
>> OsiCpxSolverInterface::basisIsAvailable() calls CPXsolninfo() and returns 
>> the value of the expression solntype == CPX_BASIC_SOLN.  So it is reporting 
>> whether there is a current solution together with basis.  Other return 
>> codes from CPXsolninfo() (according to cplex.h) are CPX_NO_SOLN, 
>> CPX_NONBASIC_SOLN, CPX_PRIMAL_SOLN.
>
>
> I wrote that code. I did it in this way, since there is already a

Sorry, I should have checked the history.  I knew I didn't write it.

> method canDoSimplexInterface() that tells you if accessing the basis is 
> possible or not with that solver. Moreover, when using Cplex,
> before accessing solution info (optimal solution, optimal basis and the like)
> you should check if they are available. It seemed natural to do that
> in basisIsAvailable().

There's certainly no need to duplicate canDoSimplexInterface() with 
isBasisAvailable().  In fact, it seems like a bad idea to me.  John?

On that note, it seems like there is a proliferation of predicates these 
days.


>
> This brings up something I don't like with the current setting of 
> OsiCpxSolverInterface: For example, changing the lower bound on one variable
> makes the optimal solution disappear from the cached data and a later
> use of getColSolution() will return (silently) a zero vector. It is very 
> dangerous, as the user might use that zero vector as the optimal
> solution. It would be much better to have a method optimalInfoIsAvailable()
> that returns true iff all data related to the optimal solution/basis/reduced
> costs is up to date an available. Moreover, (but this is less important if 
> the
> method optimalInfoIsAvailable() is implemented) the method getColSolution()
> (and similar) could return an integer indicating if the operation was 
> successful or not, similar to what Cplex and Xpress do.

Well, yeah.  Or at least if there is no solution, return 0 (NULL) instead 
of &solution[0].  I forget right now what motivated the current 
architecture.  But in fact, desn't isOptimal() tell you that there is a 
solution available and that it is optimal?

>
> One might add that removing from cached data the upper bound and cost 
> function
> when changing a single lower bound on a variable seems weird. It would be
> better (and faster and safer) to update the cached data and flag the status 
> of the optimal info as not available.

Yep, agree here too.  The original caching implementation was a quick 
hack.  But in the present OSI, caching is the responsibility of 
OsiXxxSolverInterface, so every SI has to implement its own.  It'll be 
done differently next time around, so OsiSolverInterface handles all 
caching.  Then it can be done once correctly.

>
> Francois
>
>
>> 
>>> From the CPXsolninfo() man page, one parameter is:
>> 
>>    [a] pointer to an integer variable indicating the type of solution
>>    currently available. Possible return values are CPX_BASIC_SOLN,
>>    CPX_NONBASIC_SOLN, CPX_PRIMAL_SOLN, and CPX_NO_SOLN, meaning the model
>>    either has a simplex basis, has a primal and dual solution but no
>>    basis, has a primal solution but no corresponding dual solution, or
>>    has no solution, respectively.
>> 
>> The status is valid until the problemis destroyed or the solution is 
>> rendered invalid by problem mods.
>> 
>> Originally, Francois wrote:
>> 
>>> 
>>> 
>>> The function OsiClpSolverInterface::basisIsAvailable() always returns
>>> true. This is a little bit dangerous. If modifications are made to the
>>> solver after the last optimization (change of bound on variables, in
>>> particular), the available basis might be (primal or dual, or both)
>>> infeasible.
>>> 
>>> Then, calling cut generators such as Gomory and Reduce-and-Split might
>>> result in invalid cuts. The only way (as far as I can tell) to prevent
>>> this
>>> is to rely on basisIsAvailable() to stop the cut generator if the current
>>> basis is not optimal anymore.
>>> 
>>> Cplex is tracking the status of the basis accurately, but Clp does not.
>>> Is it possible to fix that?
>> 
>> -- 
>> 		Matthew Saltzman
>> 
>> Clemson University Math Sciences
>> mjs AT clemson DOT edu
>> http://www.math.clemson.edu/~mjs
>> 
>> 
>

-- 
 		Matthew Saltzman

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