Direkt zum Inhalt

Lexikon der Mathematik: Polyederkombinatorik

Teilbereich der Theorie zur Lösung ganzzahliger Optimierungsprobleme.

Ein Hauptanliegen dabei ist es, ein kombinatorisches Optimierungsproblem dadurch zu behandeln, daß man eine möglichst vollständige Charakterisierung (der Facetten) der konvexen Hülle conv(X) aller ganzzahligen zulässigen Punkte X erhält. Die dahinterstehende Hoffnung ist die Möglichkeit einer Reduktion des Ausgangsproblems auf eine lineare Programmierungsaufgabe – was natürlich nicht immer durchführbar ist. Ein wesentliches Problem dieses Zugangs ist das folgende: Finde zu einem Punkt xconv(X) eine Facette von conv(X), die x von letzterer Menge trennt.

Nach einem Resultat von Grötschel, Lovász und Schrijver ist das Ausgangsproblem genau dann in polynomialer Zeit lösbar, wenn es die obige Trennungsaufgabe ist.

Abbildung 1 zum Lexikonartikel Polyederkombinatorik
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Die Facette g trennt x von conv(X)

Auch wenn für viele kombinatorische Probleme die Charakterisierung der oben erwähnten konvexen Hülle vermutlich nicht effizient möglich ist, so haben die Untersuchungen gemäß dieser Ideen doch die schnelle Behandlung gewisser Teilfamilien von Facetten, und damit auch verbesserte Algorithmen für eine Reihe schwieriger Probleme ermöglicht.

[1] Bachem, A.; Grötschel, M.: New aspects of polyhedral theory. In: Modern Applied Mathematics. Optimization and Operations Research, North-Holland, 1982.
[2] Pulleyblank, W.R.: Polyhedral combinatorics. In: Mathematical Programming, the State of the Art, Springer, 1983.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.