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\}$.
