School Seminars and Colloquia

Orbitopal Symmetries

School Seminar

by Timo Berthold


Institution: Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
Date: Fri 7th November 2008
Time: 2:00 PM
Location: Room 213, Richard Berry Building, The University of Melb

Abstract: Symmetries are present in many integer linear programs (IP), but they are usually not desirable, since they derogate the performance of state-of-the-art IP-solvers. We summarize how symmetries in general IPs may be handled and how they may be detected. Special symmetries, for which blocks of variables encode an assignment structure, can be effectively handled with so-called orbitopes. We present two approaches to handle orbitopal symmetries: One is based on separating symmetry breaking inequalities, one applies constraint propagation. Furthermore, we introduce an algorithm that detects orbitopal symmetries. It bases on the analysis of the IP's constraint graph. We show that in general, the detection of orbitopal symmetries is as hard as the graph isomorphism problem for bipartite graphs, but can be performed in linear time under certain assumptions.

For More Information: Contact: Kerem Akartunali kerema@ms.unimelb.edu.au