- This event has passed.
ALOP Colloquium with Christopher Hojny, TU Darmstadt
1. July 2019 / 16:00 - 18:00
On Monday, July 1 2019 at 16:00 c.t. Dr. Christopher Hojny, TU Darmstadt will present his recent work entitled Symmetry Handling in Binary Programs – Combining Symretopes and Orbital Fixing
Abstract:
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 consider symretopes, 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 symresacks can 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.
The presentation will take place in HS 9.
Please join us for coffee at 15:45 in E10.