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.
Periode | 25 nov. 2021 |
---|---|
Evenementstitel | DIAMANT Symposium Autumn 2021 |
Evenementstype | Seminarie |
Locatie | Utrecht, NederlandToon op kaart |
Mate van erkenning | Nationaal |