Opened 3 years ago
Closed 3 years ago
#178 closed defect (invalid)
MIP Integer Optimality Tolerance (ratioGap) Not Respected
Reported by: | mforness | Owned by: | tkr |
---|---|---|---|
Priority: | major | Component: | Cbc |
Version: | 2.9.4 | Keywords: | |
Cc: |
Description
I’ve created a MIP model with Excel's OpenSolver? add-in that solves with Cbc. I have the ratioGap (“Branch and Bound Tolerance (%)” setting in OpenSolver?) set to 0.1%. However the solution returned by Cbc does not seem to respect this tolerance setting. For example, when I solve the continuous/relaxed linear model, the objective value being minimized is solved to 3,613,245. But with the ratioGap set to 0.001, the model returns a solution of 8,388,236, well outside the 0.1% tolerance I was expecting. I’ve set ratioGap to various other settings with similar results. At this point I am not sure if I'm encountering a bug, or if I have issues within my model.
I have attached the lp model file, the sol solution file, and the OpenSolver? log file.
Brief model explanation: this is a production scheduling MIP model designed to determine the production location for each piece of demand in a way that minimizes lead time to the customer, subject to capacity constraints, with penalty costs added for exceeding capacity. The decision variables for ‘production quantity’ are constrained to integers. This is still loaded with test data.
Note that I also created an overly simplified version of the model to test a similar structure to see if I could better isolate the error. I again encountered Cbc returning a solution outside of the specified integer tolerance % (even with the tolerance set to 0%, the solution returned was 4.2% larger than the continuous/relaxed solution).
Attachments (3)
Change History (6)
Changed 3 years ago by mforness
Changed 3 years ago by mforness
Changed 3 years ago by mforness
comment:1 Changed 3 years ago by tkr
comment:2 Changed 3 years ago by mforness
You're absolutely right. I was misinterpreting the ratioGap parameter as the gap from the LP relaxation bound. Thanks for the quick response and correction!
comment:3 Changed 3 years ago by tkr
- Resolution set to invalid
- Status changed from new to closed
I'm a bit confused by what you wrote. I guess you are misunderstanding the definition of gap or the meaning of the ratioGap parameter. What ratioGap indicates is the target final gap to be achieved before the solver terminates. The gap is not from the LP relaxation bound but rather from the current lower bound yielded by the branch and bound tree. In the log you attached, that lower bound is 8383089.8, which results in a gap of .0019, (roughly) as expected. This mean there can't be a solution with value smaller than 8383090, which is very close to the obtained solution. There can be a number of reasons why Cbc doesn't achieve the precise gap requested, but the result is certainly acceptable, given the imprecision of floating point computation.