A Unified Framework for Symmetry Handling.

Abstract: 

Discrete optimization problems are often solved using constraint programming or mided-integer programming techniques, using enumeration or branch-and-bound techniques. It is well known that if the problem formulation is very symmetric,  there may exist many symmetrically equivalent solutions to the problem. Without handling the symmetries, traditional solving methods have have to check many symmetric parts of the solution space, which comes at a high computational cost.

Handling symmetries in optimization problems is thus essential for devising efficient solution methods. In this presentation, we present a general framework that captures many of the already existing symmetry handling methods. While these methods are mostly discussed independently from each other, our framework allows to apply different symmetry handling methods simultaneously and thus outperform their individual effects. Moreover, most existing symmetry handling methods only apply to binary variables. Our framework allows to easily generalize these methods to general variable types. Numerical experiments confirm that our novel framework is superior to the state-of-the-art methods implemented in the solver SCIP.

Posted on Oct 2, 2023 in ACGO, Seminars