[Coin-discuss] OsiCpx optimality for MIPs
Ted Ralphs
tkralphs at lehigh.edu
Fri Jan 28 15:23:41 EST 2005
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,
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."
More information about the Coin-discuss
mailing list