Abstract:

A symmetry of a mixed-integer nonlinear program (MINLP) is a bijective map that transforms feasible solutions into feasible solutions while preserving the objective value. Already for linear problems it is well known that symmetries can negatively impact the performance of branch-and-bound methods, since symmetric regions of the search space will be repeatedly explored without providing new information. Most of the existing approaches for detecting symmetries focus on permutation symmetries that exchange the order of entries in a solution vector. For many problems classes, however, permutation symmetries do not capture all symmetries. For example, when packing objects into rectangular containers, also reflection symmetries of the container can be taken into account.

In this talk, we present a novel mechanism for computing, next to permutation symmetries, also reflection and translation symmetries of MINLPs. As existing approaches for permutation symmetries, we introduce a suitable graph whose automorphisms correspond to symmetries of a MINLP. Since reflection symmetries may nontrivially interact with nonlinear functions of a MINLP, however, our graph is much more involved than the previously known symmetry detection graphs. We also briefly discuss generalizations of state-of-the-art symmetry handling methods to reflection symmetries. The talk is concluded by numerical experiments showing the effect of handling reflection symmetries in the MINLP solver SCIP.

Bio:
Christopher Hojny is an assistant professor working at TU/e since 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.