Noch Fragen? 0800 / 33 82 637

Symmetries in Binary Programs

A Polyhedral Perspective

Produktform: E-Buch Text Elektronisches Buch in proprietärem

Branch-and-bound is a well-established tool for solving binary programs. If symmetries are present, however, even instances of moderate size may be hard to solve. For this reason, several techniques to handle symmetries have been developed. This thesis reviews existing symmetry handling techniques and develops a problem specific approach to handle symmetries in a graph coloring problem. Afterwards, in the main part of the thesis, two families of 0/1-polytopes are introduced that allow for deriving symmetry handling inequalities for arbitrary applications: symretopes and symresacks. In an extensive polyhedral study, facet defining inequalities and integer programming formulations of symretopes and symresacks are derived that can be used to completely handle symmetries in branch-and-bound. In particular, the derived inequalities are numerically very stable because all their coefficients are either 0 or U+00B11. Moreover, this thesis shows how problem structure can be incorporated into symresacks to find stronger cutting planes in certain applications. The developed techniques have been implemented using the integer programming framework SCIP. An extensive numerical study using benchmarking instances as well as instances that arise in applications demonstrates the effectiveness and competitiveness of the developed techniques.weiterlesen

Elektronisches Format: PDF

Sprache(n): Englisch

ISBN: 978-3-9654800-1-8 / 978-3965480018 / 9783965480018

Verlag: sierke VERLAG - Sierke WWS GmbH

Erscheinungsdatum: 15.11.2018

Seiten: 202

Auflage: 1

Autor(en): Christopher Hojny

58,00 € inkl. MwSt.
kostenloser Versand

lieferbar - Lieferzeit 10-15 Werktage

zurück