Symmetries in Binary Programs

A Polyhedral Perspective
sierke VERLAG - Internationaler Wissenschaftsverlag
  • 1. Auflage
  • |
  • erschienen am 15. November 2018
  • Buch
  • |
  • Softcover
  • |
  • 202 Seiten
978-3-96548-000-1 (ISBN)
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.
  • Englisch
  • Für höhere Schule und Studium
  • |
  • Für Beruf und Forschung
  • Höhe: 25 cm
  • |
  • Breite: 17.6 cm
  • 380 gr
978-3-96548-000-1 (9783965480001)
weitere Ausgaben werden ermittelt

Versand in 10-20 Tagen

58,00 €
inkl. 7% MwSt.
in den Warenkorb