Detecting and handling reflection symmetries in mixed-integer (nonlinear) programming and beyond

Symmetries in mixed-integer (nonlinear) programs (MINLP), if not handled appropriately, are known to negatively impact the performance of (spatial) branch-and-bound algorithms. Usually one thus tries to remove symmetries from the problem formulation or is relying on a solver that automatically detects and handles symmetries. While modelers of a problem can handle various kinds of symmetries, automatic symmetry detection and handling for MINLP is mostly restricted to permutation symmetries. This article therefore develops techniques such that also black-box solvers can automatically detect and handle a broader class of symmetries. Inspired from geometric packing problems like the kissing number problem, we focus on reflection symmetries of MINLPs. We develop a generic and easily applicable framework to automatically detect reflection symmetries of MINLPs and more general mathematical programs. To handle this broader class of symmetries, we discuss generalizations of state-of-the-art methods for permutation symmetries, and develop dedicated symmetry handling methods for special reflection groups. Our symmetry detection framework has been implemented in the open-source solver SCIP and we provide a comprehensive discussion of the implementation. The article concludes with a detailed numerical evaluation of our symmetry handling methods when solving MINLPs.