Handling and Exploiting Symmetry in Benders Decomposition

Abstract

Benders decomposition (BD) is a framework for solving optimization problems by removing some variables and modeling their contribution to the original problem via so-called Benders cuts. While many advanced optimization techniques can be applied in a BD framework, one central technique has not been applied systematically in BD: symmetry handling. The main reason for this is that Benders cuts are not known explicitly but only generated via a separation oracle. In this work, we close this gap by providing a framework of symmetry detection within the BD framework. To this end, we introduce a tailored family of graphs that capture the symmetry information of both the Benders master problem and the Benders oracles. Once symmetries of these graphs are known, which can be found by established techniques, classical symmetry handling approaches become available to accelerate BD. We complement these approaches by devising techniques for the separation and aggregation of symmetric Benders cuts by means of tailored separation routines and extended formulations. Both substantially reduce the number of executions of the separation oracles. In a numerical study, we show the effect of both symmetry handling and cut aggregation for bin packing and scheduling problems.

Biography

Christopher Hojny is an assistant professor whose main research field is computational integer programming. After obtaining his PhD degree at TU Darmstadt in 2018, he moved to TU/e in October 2019. His main research topic is the development of efficient techniques to handle symmetries in mixed-integer programs. Besides symmetry handling, he is also interested in theoretical properties of integer programs (e.g., the existence of formulations with certain properties) and developing integer programming approaches to solve combinatorial optimization problems. Christopher is also a co-developer of the academic solver SCIP and serves on the board of the Mixed-Integer Programming Society as well as Associate Editor of Mathematical Programming Computation.