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 x ∉ conv(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.
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.
Schreiben Sie uns!