ALOP-Kolloquium: Symmetry Handling in Binary Programs -Combining Symretopes and Orbital Fixing

Im Rahmen des Kolloquiums des Graduiertenkollegs Algorithmic Optimization findet am

Montag, dem 01.Juli 2019
16:00 Uhr c.t.
Hörsaal 9

folgender Vortrag statt:

Symmetry Handling in Binary Programs -Combining Symretopes and Orbital Fixing
Dr. Christopher Hojny, TU Darmstadt

Branch-and-bound is an established method to solve binary programs with thousands of variables in adequate time. If symmetries are present, however, even small instances may be hard to solve, because symmetric parts of the branch-and-bound tree are inspected repeatedly without providing new information. A standard way to handle symmetries in binary programs is to add inequalities that cut off solutions that are lexicographically not maximal in their symmetry classes (orbits).In this talk, we focus on an approach that generalizes most of the known inequalities. We considersymretopes, which are the convex hull of all binary vectors that are lexicographically maximal in their orbits. Thus, adding inequalities of an IP formulation for symretopes to a binary program removes all the symmetry of the program. To derive a tractable IP formulation, we consider symresacks, which are knapsack polytopes that are defined by a single symmetry handling inequality. We prove that the optimization problem over symresacks and the separation problem of minimal cover inequalities for symresackscan be solved in almost linear time. This yields an efficiently separable and numerical stable IP formulation of symretopes.Another way to handle symmetries is to fix binary variables if one can show that fixing the variables to the complementary value cannot lead to a lexicographically maximal solution, so-called orbital fixing. While symmetry handling inequalities and orbital fixing are incompatible, in general, we demonstrate how both can be used in parallel if the corresponding problem decomposes in an appropriate way. Numerical experiments show that using both approaches simultaneously improves on using either of these methods.

Prof. Dr. Martin Schmidt

( Aushang​​​​​​​ )

Kolloquiums Kaffee ab 15:45 Uhr im Raum E 10