A Closest Benders Cut Selection Scheme for Accelerating the Benders Decomposition Algorithm

Abstract

The Benders decomposition algorithm often shows poor convergence. To improve the convergence of the Benders decomposition algorithm. Recently, it was proposed the use of feasibility cuts closest to a solution in the set defined by all feasibility cuts. We extend this feasibility cut selection scheme to a new cut selection scheme for optimality cuts and propose a new Benders separation framework that a single linear programming problem can solve. We show that optimality cuts generated by this scheme are Pareto optimal when some conditions are satisfied. Theoretical connections to the existing Benders cut generation methods are also identified. Extensive computational experiments on the multiple classes of benchmark problems demonstrate that the proposed algorithm improves the convergence speed and computational time. Summary of Contribution: The Benders decomposition algorithm is one of the most widely used algorithms in operations research. However, the Benders decomposition algorithm often shows poor convergence for some optimization problems. In this paper, to improve the convergence of the Benders decomposition algorithm, we propose a unified closest Benders cut generation scheme. We give theoretical properties of the proposed Benders cuts, including Pareto optimality and facet-defining conditions. Also, we conducted extensive computational tests on various instances, such as network design and expansion problems. The results show the effectiveness of the closest Benders cut compared with existing algorithms and Cplex.