A Closest Benders Cut Selection Scheme for Accelerating the Benders Decomposition Algorithm
针对Benders分解算法收敛慢的问题，提出一种统一的最接近Benders割生成方案，包括最优性割的选择，理论证明其帕累托最优性，并在网络设计等基准问题上验证了加速效果。
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.