A novel Pareto-optimal cut selection strategy for Benders Decomposition

Abstract Decomposition methods can be used to create efficient solution algorithms for a wide range of optimization problems. For example, Benders Decomposition can be used to solve scenario-expanded two-stage stochastic optimization problems effectively. Benders Decomposition iteratively generates Benders cuts by solving a simplified version of an optimization problem, the so-called subproblem. The choice of the generated cuts can impact the performance of this approach. Several approaches to making this choice are known. The Magnanti-Wong method focuses on generating Pareto-optimal cuts. Cuts based on minimal infeasible subsystems of a modified version of the subproblem have been proven to be effective. Additionally, methods that use facets of the subproblem ’s value function epigraph have been developed recently. We have made a contribution to the field of cut selection strategies for Benders Decomposition by introducing a novel concept of Pareto-optimality, which leads to an efficient cut selection strategy. This strategy aims for cuts that exclude a large set of points from being optimal. Furthermore, we have established the algorithmic framework to fully leverage the potential of our cut selection strategy. We have compared our cut selection strategy with several others on various instances, including instances from the MIPLib, network design problems, and randomly generated mixed-integer linear programs. The computational results indicate that our method solves problems faster than the benchmark approaches, particularly when combined as a hybrid selection strategy with the minimal infeasible subsystem cut selection. Moreover, the method clearly outperforms the other cut selection strategies in terms of the number of cuts required to solve a problem optimally. Therefore, this method is particularly effective in situations with limited memory or in cases where the subproblem is challenging to solve.