Whats the difference between MIP solution and Final Solve? I am trying to benchmark some solution approaches and I am not sure which of those is the more significant... sometimes they have the same value.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
By default, Gams/Cplex will try to calculate duals by fixing the integer variables and then resolving as an LP. This is the "final solve". Usually the objectives are the same. In rare cases the final lp can be infeasible or the objective can be different because of an artifact in Cplex (mind-numbing detail: it can return mip solutions obeying the gap tolerance that are not lp optimal but found heuristically; in that case the final lp can improve the mip solution).
answered Dec 10, 2020 at 20:25
$\begingroup$
$\endgroup$
3
While ago, I asked such a question and GAMS answer was:
I try solving a VRP problem with the below results without the gap option:
Iteration log . . .
Iteration: 1 Dual objective = 124.000000
Root relaxation solution time = 0.00 sec. (0.10 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
36 11 integral 0 497.0000 390.9714 269 21.33%
Found incumbent of value 497.000000 after 0.05 sec. (4.06 ticks)
Solution satisfies tolerances.
MIP Solution: 497.000000 (444 iterations, 74 nodes)
Final Solve: 497.000000 (0 iterations)
Best possible: 448.352400
Absolute gap: 48.647600
Relative gap: 0.097882
*-----------------------------------------------------------------------------------------------------
When I use the gap option:
Iteration log . . .
Iteration: 1 Dual objective = 124.000000
Root relaxation solution time = 0.00 sec. (0.10 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
36 11 integral 0 497.0000 390.9714 269 21.33%
Found incumbent of value 497.000000 after 0.05 sec. (4.06 ticks)
Proven optimal solution.
MIP Solution: 497.000000 (470 iterations, 80 nodes)
Final Solve: 497.000000 (0 iterations)
Best possible: 497.000000
Absolute gap: 0.000000
Relative gap: 0.000000
The answer:
The gap that you highlighted is not the final one from when the solver
terminated.
With the default settings (which is optcr=0.1), you got
Solution satisfies tolerances.
MIP Solution: 497.000000 (444 iterations, 74 nodes)
Final Solve: 497.000000 (0 iterations)
Best possible: 448.352400
Absolute gap: 48.647600
Relative gap: 0.097882
That is, the remaining relative gap is 10%, which is just below optcr=0.1.
CPLEX enumerated 74 nodes in the B&B tree to get to this gap.
When you set optcr=0, you got
Proven optimal solution.
MIP Solution: 497.000000 (470 iterations, 80 nodes)
Final Solve: 497.000000 (0 iterations)
Best possible: 497.000000
Absolute gap: 0.000000
Relative gap: 0.000000
That is, CPLEX did not stop when the gap falls below 10% but continued
until it could bring down the gap to 0.
It had to enumerate 80 nodes in the B&B tree for this.
For more details please, see this link. I hope it would be helpful.
-
$\begingroup$ That is just a question of Cplex not logging the final solution. The lines with "Absolute gap" and "Relative gap" are the correct gaps for the returned solution. A further complicating detail is that Gams uses a slightly different definition for the relative gap than Cplex does. $\endgroup$ Commented Dec 10, 2020 at 20:48
-
$\begingroup$ @Dr. Kalvelagen, that's right but, for solving the mentioned problem I tried to use both GAMS/CPLEX and CPLEX/OPL. and based on what you mentioned, the definition of the GAP between those is a bit different. This is why I asked this question. đź‘Ť $\endgroup$– A.OmidiCommented Dec 10, 2020 at 21:00
-
$\begingroup$ why it is giving different values (i.e 497 and 498.3524) of best possible when you are using optcr and not using optcr? $\endgroup$– RaviCommented May 29, 2022 at 19:38