Symmetry handling in binary programs through propagation

  • M.J. van Doornmalen (Spreker)

Activiteit: Types gesprekken of presentatiesAangemelde presentatieWetenschappelijk

Beschrijving

Symmetries of binary programs are known to dramatically slow down branch-and-bound procedures. A classical approach is to add symmetry handling inequalities that cut off all solutions that are not lexicographically maximal in their symmetry class.
In this talk, we present a propagation-based symmetry handling technique to ensure only lexicographically maximal solutions for permutations and groups acting on binary variables are found. Given certain initial variable fixings, e.g. branching decisions at a node of the branch-and-bound tree, the goal is to find valid additional fixings ensuring that integral solutions are lexicographically maximal in their symmetry class. We devise efficient algorithms that find possible fixings for sets of permutations, and for various classes of symmetry groups. In some cases, we are able to find all possible fixings. Last, we discuss the computational effectiveness of our methods.
Periode25 nov. 2021
EvenementstitelDIAMANT Symposium Autumn 2021
EvenementstypeSeminarie
LocatieUtrecht, NederlandToon op kaart
Mate van erkenningNationaal