3
$\begingroup$

Suppose I have a mixed-integer-linear programming model where the objective is maximization. I solve my model in two different ways. First, I call CPLEX (a commercial solver), and then implement Benders decomposition in the traditional way (not with the single tree version).

What I mean by saying "traditional" is that I solve the master problem (MP) to optimality where the optimal provides an upper bound (UP). Then, a Benders cut (feasibility of optimality) is generated from the subproblem (SP) and a lower bound (LB) is obtained (not necessarily improved at every iteration). The MP is updated with the Benders cut. This process is repeated until a certain criteria is met.

CPLEX can return an optimality gap larger than 100 since the optimality gap is calculated as |bestbound-bestinteger|/(1e-10+|bestinteger|).

https://www.ibm.com/docs/en/icos/12.7.1.0?topic=parameters-relative-mip-gap-tolerance

However, the optimality gap in Benders is calculated as (UB-LB)/UB. In other words, it is guaranteed to be between 0 and 100 with the correct scaling.

My question is how one can make a fair comparison between solving a model with a commercial solver and Benders with respect to optimality gaps?

Suppose the objectives of MP and SP are $\max c^Tx +\gamma$ and $\min \beta$, respectively, then $UB=c^Tx +\gamma$, which is non-increasing at each iteration. As for the LB, it is calculated as $LB = \max\{LB, c^Tx + \beta\}$.

$\endgroup$
6
  • $\begingroup$ First, are you maximizing or minimizing? Second, when you say the optimality gap in Benders is calculated a certain way, who or what is doing that calculation? What is stopping you from calculating it the same way CPLEX does? $\endgroup$
    – prubin
    Oct 10 at 18:35
  • $\begingroup$ Also, are you using the "classical" version of Benders (solve master to optimality, add cut, start over) or the "contemporary" or "one tree" version (solve the master once, using callbacks to add Benders cuts on the fly)? $\endgroup$
    – prubin
    Oct 10 at 18:47
  • $\begingroup$ @prubin I updated the post after your comments. How can I calculate the optimality gap with Benders in the same way CPLEX does? Isn't the (UB-LB)/UB correct way of calculating the optimality gap in Benders? $\endgroup$
    – whitepanda
    Oct 10 at 19:00
  • $\begingroup$ I agree that the most recent master solution is an upper bound for the optimum, but I don't see where you are getting the lower bound. $\endgroup$
    – prubin
    Oct 10 at 19:57
  • $\begingroup$ @prubin I added how to calculate both upper and lower bounds for a maximization problem. As a reference, please see Page 2 at web.stanford.edu/class/msande348/papers/bendersingams $\endgroup$
    – whitepanda
    Oct 10 at 20:12
2
$\begingroup$

Assuming you are comparing Benders results to CPLEX solutions, why not use the CPLEX formula for the Benders results? Best integer would be your $LB$ and best bound would be the current objective value of the master problem.

$\endgroup$
1
  • $\begingroup$ Ohh okay! That makes sense. I misread your comment. Thanks! $\endgroup$
    – whitepanda
    Oct 11 at 12:37

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.