Schnittebenenverfahren

Problemdefinition

Ein Schnittebenenverfahren dient zur Lösung ganzzahliger Programme (engl. integer program, IP) in der Normalform

Dabei ist A eine reelle Matrix und b und c sind Vektoren passender Dimension. Die Bedingung ist komponentenweise zu verstehen, also als

für alle Zeilen i der Matrix A. Genauso bedeutet die Bedingung , dass alle Einträge des Vektors x nichtnegativ sein müssen.

die durch Weglassen der Ganzzahligkeitsbedingungen entsteht, bildet ein konvexes Polyeder im n-dimensionalen Raum, dessen beschränkende Hyperebenen den Zeilen des Ungleichungssystems entsprechen. P enthält u. a. alle zulässigen Punkte des Ausgangssystems, also alle ganzzahligen Punkte, die die Bedingungen erfüllen, aber im Unterschied zur linearen Optimierung sind nicht alle Punkte in P zulässig. Das lineare Programm

wird als LP-Relaxierung des ganzzahligen Problems bezeichnet.

Im nebenstehenden Bild ist das ganzzahlige lineare Programm (IP)

dargestellt. Die zulässigen ganzzahligen Punkte sind rot eingezeichnet, und die rot gestrichelten Linien kennzeichnen ihre konvexe Hülle, also das kleinste Polyeder, das alle diese Punkte enthält. Über diesem Polyeder soll eigentlich optimiert werden, aber es ist meist nicht genau bekannt. Die blauen Linien zusammen mit den Koordinatenachsen begrenzen das Polyeder P der LP-Relaxierung, das durch das Ungleichungssystem ohne Ganzzahligkeitsbedingungen gegeben ist. Ziel der Optimierung ist es, die schwarz gestrichelte Linie so weit parallel nach oben (in Richtung des Vektors c = (0;1)) zu verschieben, dass sie das jeweilige Polyeder gerade noch berührt. Die Optimallösungen des ganzzahligen Problems sind also die Punkte (1;2) und (2;2) mit dem Zielfunktionswert c^T x = (0;1)^T (1;2) = 2. Die – in diesem Fall eindeutige – optimale Lösung der LP-Relaxierung mit dem Zielfunktionswert 2,8 ist der blau markierte Punkt LP_opt = (1, 8;2, 8), der nicht ganzzahlig und damit auch nicht zulässig für das IP ist.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Schnittebenenverfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung