Glomb L, Liers-Bergmann F, Rösel F (2024)
Publication Status: In review
Publication Type: Unpublished / Preprint
Future Publication Type: Journal article
Publication year: 2024
Decomposition approaches can be used to generate practically efficient solution algorithms for
a wide class of optimization problems. For instance, scenario-expanded two-stage stochastic optimization
problems can be solved efficiently in practice using Benders Decomposition. The performance of the
approach can be influenced by the choice of the cuts that are added during the course of the algorithm.
The so-called Magnanti-Wong method aims for Pareto-optimal cuts. Cuts based on minimal infeasible
subsystems of a modified version of the sub problem have proven to provide strong cuts. Most recently,
methods using facets of the sub problem’s value function’s epigraph have been developed.
We contribute to the field of cut selection strategies for Benders Decomposition by developing an innovative notion of Pareto-optimality, which implies an efficient cut selection strategy. The strategy aims
for cuts that exclude a large set of points from being optimal. We further develop the algorithmic framework to exploit the potential of our cut selection strategy optimally. We benchmark our cut selection
strategy against several other cut selection strategies on various instances. Some instances are taken from
the MIPLib, some others are network design problems, and others are randomly generated mixed-integer
linear programs. The computational results show that the developed method is, measured in CPU seconds
needed to solve a problem to optimality, at least competitive for or better than the benchmark approaches
for all three instance classes, especially, when it is combined as hybrid selection strategy with the minimal
infeasible subsystem cut selection. In addition, the method clearly outperforms the other cut selection
strategies measured in the number of cuts needed to solve a problem to optimality. Hence, the method is
especially effective in situations with scarce memory or with a sub problem that is difficult to solve
APA:
Glomb, L., Liers-Bergmann, F., & Rösel, F. (2024). A novel Pareto-optimal Cut Selection Strategy for Benders Decomposition. (Unpublished, In review).
MLA:
Glomb, Lukas, Frauke Liers-Bergmann, and Florian Rösel. A novel Pareto-optimal Cut Selection Strategy for Benders Decomposition. Unpublished, In review. 2024.
BibTeX: Download