[Coin-discuss] OsiCpx optimality for MIPs

[Matthew Saltzman]

On Fri, 28 Jan 2005, Ted Ralphs wrote:

> Matthew Saltzman wrote:
>> On Fri, 28 Jan 2005, Brady Hunsaker wrote:
>> 
>>> I just ran into a quirk with OsiCpx solving a MIP.  CPLEX 9.0 has default 
>>> gap parameters so that it stops the branch-and-bound process if the gap 
>>> gets within 0.01% or an absolute value of 0.000001.
>>> 
>>> This caused the solution process to stop, but OsiCpx->isProvenOptimal() 
>>> returned false, because CPLEX returns a separate return code 
>>> (CPXMIP_OPTIMAL_TOL) for this situation.
>>> 
>>> I believe this should be corrected.  I can see two possible solutions:
>>> 1. Reply true to isProvenOptimal() if CPXMIP_OPTIMAL_TOL is returned, even 
>>> though this is technically incorrect.
>>> 2. Explicitly set the gap parameters to 0 in branchAndBound().
>>> 
>>> I'm using the first solution right now, but I'd like to hear any other 
>>> opinions, especially from OsiCpx maintainers.
>>> 
>>> Brady
>> 
>> 
>> My first reaction is in favor of solution 1.
>> 
>> (1) Overriding tolerances that users may have reason to set is a bad idea.
>> 
>> (2) Most users probably would accept that a solution that's within 
>> tolerance is optimal "for all practical purposes".  If a user wants a 
>> guarantee of optimality, he can set CPXMIP_OPTIMAL_TOL to zero himself.
>> 
>> Is this a small enough example to pass around for testing?  I wonder how 
>> other solver/SI combinations handle this issue.
>> 
>
> Setting the optimality tolerance to zero does not likely guarantee an optimal 
> solution either, unless the LP solver is using rational arithmetic to obtain 
> a verifiable lower bound. It would be nice to require that the solver produce 
> a verifiable optimal solution, but no solver that I know of actually does 
> this in reality. To be practical, we are forced leave it up to the solver to 
> determine what it means for a solution to be optimal. Given that, it seems to 
> make sense that isProvenOptimal() should apply that same condition when 
> responding to the query.
>
> Cheers,

So is that an argument for solution 1 or something else?  It seems that 
the point is that CPLEX has return codes for "really, really optimal" and 
"sorta, kinda optimal enough, I guess", but OSI only has "optimal".

It seems clear that solution 2 is a bad idea.

>
> Ted
>

-- 
 		Matthew Saltzman

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