2
$\begingroup$

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.

enter image description here

$\endgroup$
5
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Dec 10 '20 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.Omidi
    Dec 10 '20 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.