[Coin-discuss] OsiCpx optimality for MIPs

[Brady Hunsaker]

Given that solution 1 seems to be the consensus choice (at least of 
early responders), I'd ask an OsiCpx maintainer to update the code as 
follows:

Lines 460-463 of OsiCpxSolverInterface.cpp should now be:
   return ((probtypemip_ == false &&
	  (stat == CPX_STAT_OPTIMAL || stat == CPX_STAT_OPTIMAL_INFEAS)) 	  || 
(probtypemip_ == true &&
	  (stat == CPXMIP_OPTIMAL || stat == CPXMIP_OPTIMAL_TOL)));

This just adds the CPXMIP_OPTIMAL_TOL.

Brady


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.
> 
>>
>> Ted
>>
> 


-- 
Brady Hunsaker
Assistant Professor
Industrial Engineering
University of Pittsburgh
http://www.engr.pitt.edu/hunsaker/