[Coin-discuss] OsiCpx optimality for MIPs

[Ted Ralphs]

Matthew Saltzman wrote:
> 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.

Yes, I suppose it's an argument for solution 1, or at least against 
solution 2 :). Of course, the user can override the termination 
criteria, but whatever termination criteria was being used by the solver 
at the time the (supposedly optimal) solution was generated, the same 
logic should be applied in isProvenOptimal(). This view of things 
probably only applies with the current interface, though. A more general 
interface might explicitly support the generation of suboptimal 
solutions or solutions satisfying a given tolerance rather then only 
having the option to generate "optimal" solutions. Then perhaps the 
answer is a little different. Something for OSI2...

Ted
-- 
Dr. Ted Ralphs
Assistant Professor
Industrial and Systems Engineering
Lehigh University
(610)758-4784
tkralphs at lehigh.edu
www.lehigh.edu/~tkr2

"An optimist is someone who thinks
'It doesn't get any better than this.'
A pessimist is someone who's afraid that's true."