A non-linear lifting procedure is proposed to generate high density Benders cuts. The new denser cuts cover more master problem variables than traditional Benders cuts, shortening the required number of iterations to reach optimality, and speeding up the Benders decomposition algorithm. To lessen the intricacy stemmed from the non-linearity, a simple outer approximation lineariza- tion is devised to allow the use of linear programming tools to solve the additional Benders subproblem. Computational experiments show that the new cut selection procedure outperforms two existing alternatives — the Pareto-optimal cuts by Papadakos (2008), and the high density Benders cuts of Tang et al (2013) — on solving two distinct location problems. Despite an extra computational effort, the worthwhile subproblem greatly reduces the number of Benders iterations when facing harder instances, yielding in remarkable time savings.
Article
View Improving Benders decomposition via a non-linear cut selection procedure