Varianten und Verbesserungen des Simplex-Verfahrens

In der hier vorgestellten Form, die im wesentlichen der ursprünglichen Version von Dantzig entspricht, wird der Simplex-Algorithmus in praktischen Implementierungen heute nicht mehr verwendet. Im Laufe der Zeit sind einige Varianten des Simplex-Verfahrens entwickelt worden, die die Rechenzeit und den Speicherbedarf beim Lösen linearer Programme gegenüber dem Standardverfahren deutlich verkürzen und numerisch deutlich stabiler sind. Die wichtigsten Verbesserungen, die heute zum Standard in guten LP-Lösern gehören, sollen hier kurz vorgestellt werden.

Auswahl des Pivotelementes

Bei der Auswahl des Pivotelements hat man in der Regel einige Freiheiten. Die Pivotspalte ss und die Pivotzeile rr können beliebig gewählt werden, unter den Bedingungen, dass
  • die Pivotspalte positive reduzierte Kosten hat und
  • die Pivotzeile wieder zu einer zulässigen Basislösung führt.
Die Wahl des Pivotelementes hat oft großen Einfluss auf die Anzahl der Iterationen und auf die numerische Stabilität des Verfahrens, insbesondere bei degenerierten Problemen. Die Entwicklung besserer Pivotstrategien, insbesondere zur Spaltenauswahl, haben im Laufe der Zeit große Fortschritte bei der Beschleunigung des Lösungsprozesses bewirkt.

Spaltenauswahl

Für die Auswahl der Pivotspalte (engl. pricing) gibt es verschiedene Strategien, die unterschiedlichen Rechenaufwand erfordern und je nach Eingabedaten unterschiedlich gut funktionieren:
  • Wähle die erste geeignete Spalte. Dies ist die einfachste Variante, die aber oft zu sehr vielen Iterationen führt und daher in der Praxis nicht verwendet wird.
  • Die ursprünglich von Dantzig vorgeschlagene Methode wählt eine der Spalten mit dem größten reduzierten Kostenwert. Diese Variante kann bei vielen Variablen viel Rechenzeit beanspruchen.
  • Das steepest-edge pricing ist eine Kombination aus Spalten- und Zeilenwahl, die zusammen den größten Fortschritt für die Zielfunktion bringen. Diese Variante ist in jeder Iteration sehr aufwändig, führt aber oft zu wenigen Iterationen.
  • Das devex pricing ist eine 1974 von Paula Harris vorgeschlagene Approximation von steepest-edge pricing und eines der Standardverfahren in heutigen LP-Lösern. Hierbei werden die Spalten der Matrix und die reduzierten Kosten vor der Auswahl auf eine einheitliche Norm skaliert, um die Aussagekraft der reduzierten Kosten zu erhöhen.
  • Beim partial pricing wird die Variablenmenge in Blöcke unterteilt und eines der obigen vorherigen Verfahren auf einen Block angewendet. Erst wenn dort keine geeignete Variable gefunden wird, wird überhaupt der nächste Block betrachtet.
  • Das multiple pricing sucht einmal eine Menge von geeigneten Variablen heraus, die dann in den nächsten Iterationen bevorzugt als Kandidaten betrachtet werden. Erst wenn keiner dieser Kandidaten mehr positive reduzierte Kosten besitzt, werden die anderen Variablen betrachtet.
  • Das partial multiple pricing ist eine Kombination der letzten beiden Varianten, die neue Kandidaten immer nur aus einem Teil aller zur Verfügung stehenden Variablen bestimmt. Diese Strategie gehört neben devex pricing heute zu den Standardstrategien.
  • Beim hybrid pricing werden mehrere Strategien je nach Situation abwechselnd verwendet. Einige LP-Löser wenden zusätzlich noch numerische Kriterien bei der Spaltenauswahl an, um die Probleme durch Rundungsfehler in Grenzen zu halten.

Zeilenauswahl

Gibt es mehrere geeignete Pivotzeilen, hat man die Wahl zwischen mehreren Varianten:
  • Wähle die erste geeignete Zeile. Diese Variante ist zwar pro Iteration sehr schnell, führt aber insgesamt oft zu vielen Iterationen und ist numerisch instabil.
  • Die lexikographische Auswahlregel wählt unter allen in Frage kommenden Zeilen die (eindeutige) lexikographisch kleinste Zeile aus. Diese Regel ist unter dem Gesichtspunkt der Geschwindigkeit nicht besonders gut, verhindert aber, dass Tableaus mehrfach besucht werden und der Algorithmus ins Zykeln gerät. Aus diesem Grund kann sie beispielsweise für einige Iterationen verwendet werden, um von einer Basislösung wegzukommen, bevor wieder auf andere Auswahlverfahren umgestellt wird.
  • Der 1973 von Paula Harris vorgeschlagene Harris-Quotiententest, der heute zu den Standardverfahren zählt, erlaubt aus Gründen der numerischen Stabilität eine leichte Unzulässigkeit der neuen Lösung.

Variablenschranken

In der Praxis müssen häufig obere und untere Schranken für die Variablen berücksichtigt werden. Dies gilt insbesondere dann, wenn lineare Programme beispielsweise im Rahmen eines Branch-and-Cut-Prozesses als Unterproblem gelöst werden. Für solche einfachen Arten von Ungleichungen wie Variablenschranken gibt es das sogenannte Bounded-Simplex-Verfahren, bei dem die Schranken direkt in den einzelnen Simplex-Schritten berücksichtigt werden. Im Gegensatz zur Standardversion, bei dem eine Nichtbasisvariable immer den Wert 0 haben, kann sie jetzt auch den Wert einer ihrer Schranken annehmen. Diese Mitführung der Schranken in den einzelnen Schritten bewirkt eine kleinere Anzahl der Zeilen und damit eine kleinere Basis gegenüber der offensichtlichen Variante, Variablenschranken als Ungleichungen in das LP zu schreiben.

Duales Simplex-Verfahren

Neben einer optimalen Primallösung, also einer Lösung für das gegebene lineare Programm, berechnet das oben beschriebene primale Simplex-Verfahren auch eine optimale Duallösung, also eine Lösung des zugehörigen dualen linearen Programms. Da das duale LP aus dem primalen im wesentlichen durch Vertauschung von Zeilen und Spalten entsteht, lässt sich mit dem Simplex-Verfahren auch das duale Problem lösen, indem man das gegenüber der obigen Variante leicht modifizierte Tucker-Tableau verwendet und im beschriebenen Algorithmus Zeilen und Spalten vertauscht. Diese Variante heißt dann duales Simplex-Verfahren. Es wurde erstmals 1954 von Lemke und Beale beschrieben, ist aber erst seit Anfang der 1990er Jahre fester Bestandteil kommerzieller LP-Löser, als erfolgreiche Pivotstrategien dafür entwickelt wurden, wie das dual steepest-edge pricing in der Version von Forrest und Goldfarb aus dem Jahre 1992.
In der Praxis hängt die Laufzeit des Simplex-Verfahrens oft im wesentlichen von der Anzahl der Zeilen im LP ab. Dies gilt insbesondere für dünnbesetzte Matrizen, wie sie in der Praxis normalerweise auftreten. Wenn ein lineares Programm sehr viele Bedingungen, aber nur wenige Variablen hat, kann es sich daher lohnen, statt dessen das duale LP zu lösen, bei dem Zeilen- und Spaltenzahl vertauscht sind, und sich dabei eine optimale Primallösung mitliefern zu lassen, die nebenbei mitberechnet wird.
Ein weiterer großer Vorteil der primal-dualen Betrachtungsweise ist es, dass primale und duale Simplexschritte abwechselnd im selben Tableau durchgeführt werden können. Anstatt das Tableau explizit zu transponieren, werden einfach im Algorithmus Zeilen- und Spaltenoperationen vertauscht, je nachdem, ob gerade der primale oder der duale Algorithmus benutzt wird. Im Gegensatz zum primalen Simplex-Verfahren, das immer eine zulässige Primallösung behält und erst am Ende eine zulässige Duallösung erreicht, ist es beim dualen Simplex-Verfahren umgekehrt. Wenn also die Primallösung zu einer Basis unzulässig, die zugehörige Duallösung aber zulässig ist, kann man durch duale Simplexschritte versuchen, wieder zu einer primal zulässigen Lösung zu kommen. Dies kann man in mehreren Zusammenhängen ausnutzen, die hier kurz beschrieben werden sollen.
  • Im Verlauf von Schnittebenenverfahren oder Branch-and-Cut-Verfahren wird sehr oft in einem gerade gelösten LP eine Variablenschranke verändert oder eine Ungleichung hinzugefügt, die von der alten Lösung nicht erfüllt wird, und anschließend das LP neu gelöst. Da die alte Basislösung jetzt nicht mehr zulässig ist, ist eine der Grundbedingungen des primalen Simplextableaus verletzt, so dass das das primale Simplexverfahren von vorne starten muss, um das neue LP zu lösen. Wenn an der Zielfunktion nichts verändert wurde, ist aber die alte Duallösung weiter zulässig, so dass mit einigen dualen Simplexschritten von der alten Startbasis aus meist nach wenigen Iterationen eine Optimallösung für das modifizierte LP gefunden wird. Dieser Unterschied schlägt sich bei großen LPs oft sehr deutlich in der Gesamtlaufzeit nieder.
  • Wenn im Verlauf des Algorithmus numerische Schwierigkeiten auftreten oder es sehr lange keinen Fortschritt in der Zielfunktion gibt, kann es sinnvoll sein, vorübergehend eine leichte Verletzung von Variablenschranken zu erlauben, um sich aus einer kritischen Ecke des Polytops hinauszubewegen. Dies kann anschließend mit einigen dualen Simplexschritten wieder behoben werden.
  • Wenn das lineare Programm bestimmte Strukturen aufweist, kann man direkt eine primal unzulässige, aber dual zulässige Startbasis angeben, ohne dafür rechnen zu müssen. In solch einem Fall kann man von dieser Basis aus direkt in Phase II mit dualen Simplexschritten starten und kann sich die Phase I sparen.

Revidiertes Simplex-Verfahren

Obwohl praktisch auftretende lineare Programme mehrere hunderttausend Variablen haben können, arbeitet das Simplex-Verfahren immer nur mit einem kleinen Teil davon, nämlich den Basisvariablen. Lediglich bei der Spaltenauswahl müssen die Nichtbasisspalten betrachtet werden, wobei es - je nach Pivotstrategie - oft ausreicht, nur einen Teil davon zu berücksichtigen. Diese Tatsache macht sich das revidierte Simplex-Verfahren zunutze, das immer nur die aktuelle Basismatrix ABA_{B} oder deren Inverse speichert, zusammen mit etwas Zusatzinformationen, aus der die aktuelle Basismatrix bzw. deren Inverse berechnet werden kann. Dadurch kommt es mit wesentlich weniger Speicherplatz aus als das ursprüngliche Tableauverfahren. Dieses Verfahren bildet heute die Grundlage mehrerer guter LP-Löser.
In der ersten kommerziellen Implementierung dieses Verfahrens von William Orchard Hays im Jahre 1954 wurde die Basisinverse noch in jedem Schritt komplett neu berechnet, was mit den damaligen Lochkartenrechnern eine Herausforderung darstellte. Wenig später implementierte er die sogenannte Produktform der Inversen nach einer Idee von A. Orden. Dabei wurde nur die erste Basisinverse gespeichert, zusammen mit Update-Vektoren, aus denen die jeweils aktuelle Inverse berechnet werden konnte. Der damalige Rekord lag bei einem linearen Programm mit 71 Variablen und 26 Ungleichungen, das innerhalb von acht Stunden optimal gelöst wurde. In heute verwendeten Implementierungen wird eher die Basismatrix selbst mit Hilfe einer speziellen Form der LR-Zerlegung gespeichert, da die Inverse einer dünnbesetzten Matrix in der Regel nicht dünnbesetzt ist,

LR-Zerlegungen

Im Verlauf des Simplex-Verfahrens werden sehr viele ähnliche lineare Gleichungssysteme gelöst. Da große lineare Gleichungssysteme auch in anderen Zusammenhängen (beispielsweise bei der Lösung von Differentialgleichungen) häufig auftreten, wurden in den 1970er Jahren in der numerischen linearen Algebra Verfahren zur LR-Zerlegung einer Matrix entwickelt. Dabei wird die Matrix in eine untere und eine obere Dreiecksmatrix zerlegt, was es anschließend erlaubt, viele Gleichungssysteme mit derselben Matrix, aber unterschiedlichen rechten Seiten effizient zu lösen.
Im Falle des Simplex-Verfahrens wird diese Methode auf die Basismatrix ABA_{B} angewandt. Da diese sich im Laufe des Simplex-Algorithmus ständig ändert, muss ihre LR-Zerlegung bei jedem Simplexschritt angepasst werden, beispielsweise mit Hilfe des nach seinen Erfindern benannten Forest-Tomlin-Updates. Diese Anpassung erfordert nur sehr geringen Aufwand im Vergleich zur Berechnung einer komplett neuen LR-Zerlegung, weil sich die Basismatrix in jeder Iteration nur in einer Spalte ändert. In praktischen Implementierungen wird meist aus numerischen Gründen trotzdem alle paar hundert Iterationen eine komplett neue LR-Zerlegung der aktuellen Matrix berechnet. Für die Berechnung der LR-Zerlegung selbst gibt es wieder verschiedene Varianten, von denen sich in der Praxis vor allem die LR-Zerlegung mit dynamischer Markowitz-Pivotisierung durchgesetzt hat, da diese die Dünnbesetztheit von Matrizen bei der Zerlegung weitgehend erhält. Dieses Verfahren hat in den letzten Jahren vor allem für große lineare Programme, die fast immer dünnbesetzt sind, zu starken Reduktionen der Rechenzeit geführt.

Preprocessing

In den letzten zehn Jahren sind durch verbessertes Preprocessing sehr große Fortschritte in den Lösungszeiten erzielt worden. Beispielsweise gibt es oft numerische Probleme, wenn in einem linearen Gleichungssystem sowohl sehr große als auch sehr kleine Zahlen auftreten. In einigen Fällen lässt sich dies durch Vorkonditionierung, also z. B. Äquilibrierung des Gleichungssystems, vor dem Start des eigentlichen Algorithmus vermeiden.
Eine andere Klasse von Methoden des Preprocessing versucht, Redundanzen im linearen Gleichungssystem zu erkennen oder Variablenschranken zu verschärfen, um die Anzahl der Zeilen und Spalten zu reduzieren:
  • Wenn eine Zeile linear abhängig von anderen Zeilen ist, ist sie überflüssig und kann entfernt werden. Dies ist allerdings - bis auf den Spezialfall, dass eine Zeile ein skalares Vielfaches einer anderen Zeile ist - im allgemeinen schwierig mit vertretbarem Aufwand zu erkennen.
  • Sehr oft sind Variablen aufgrund von Bedingungen auf einen bestimmten Wertebereich beschränkt oder durch andere Variablen festgelegt. Beispielsweise sind durch die Gleichung x1+x2=1x_{1} + x_{2} = 1 und die Nichtnegativitätsbedingungen beide Variablen auf den Bereich [0,1][0,1] beschränkt. Die Kenntnis dieser Schranke kann den Lösungsprozess beschleunigen. Darüber hinaus ist der Wert von x2x_{2} durch den Wert von x1x_{1} festgelegt. Dadurch kann man in allen Bedingungen, in denen x2x_{2} vorkommt, diese Variable durch 1−x11 - x_{1} ersetzen und x2x_{2} aus dem LP entfernen.
  • Wenn mehrere Variablen auf einen bestimmten Wertebereich fixiert wurden, kann es sein, dass einige Ungleichungen immer erfüllt sind oder nicht mehr erfüllt werden können. Im ersten Fall kann die Ungleichung entfernt werden, im zweiten Fall ist sofort die Unzulässigkeit des LPs gezeigt, und man kann aufhören.
Mit Hilfe solcher Methoden kann gerade bei sehr großen LPs die Anzahl der Zeilen und Spalten manchmal deutlich reduziert werden, was sich in sehr viel kürzeren Lösungszeiten widerspiegelt.

Laufzeit

Die Zahl der Ecken eines Polyeders kann exponentiell in der Anzahl der Variablen und Ungleichungen sein. Beispielsweise lässt sich der nn-dimensionale Einheitswürfel durch 2n2n lineare Ungleichungen beschreiben, besitzt aber 2n2^n Ecken. Klee und Minty konstruierten im Jahre 1972 einen verzerrten Einheitswürfel, den sogenannten Klee-Minty-Würfel, bei dem die von Dantzig vorgestellte Variante des Simplex-Verfahrens auch tatsächlich alle diese Ecken besuchte.Harvey J. Greenberg: Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method. University of Colorado at Denver, 1997. Ähnliche Beispiele wurden bisher für alle Zeilen- und Spaltenauswahlregeln gefunden. Dies bedeutet, dass der Simplex-Algorithmus in allen bisher bekannten Varianten im schlechtesten Fall exponentielle Laufzeit besitzt.
Bei degenerierten linearen Programmen, wie sie in der Praxis häufig auftreten, kann es sogar zum sogenannten Zykeln kommen, bei dem das Simplex-Verfahren immer wieder dieselbe Ecke betrachtet und dadurch nicht terminiert. Dies lässt sich aber durch Anwendung der lexikographischen Zeilenauswahlregel oder durch absichtliche numerische Störungen verhindern.
Aus theoretischer Sicht ist das Simplex-Verfahren daher beispielsweise den Innere-Punkte-Verfahren mit polynomialer Laufzeit unterlegen. Aus praktischer Sicht hat es sich aber in vielen Fällen als schneller erwiesen. Der größte Vorteil des Simplex-Algorithmus gegen über anderen Verfahren liegt jedoch darin, dass es bei kleinen Änderungen der Eingabedaten im Laufe des Algorithmus einen "Warmstart" erlaubt, also die letzte berechnete Basis als Ausgangspunkt für wenige weitere (primale oder duale) Iterationen nehmen kann, während beispielsweise Innere-Punkte-Verfahren in solch einem Fall von vorne anfangen müssen. Dieser Fall tritt sehr häufig auf, wenn sehr viele ähnliche lineare Programme in Folge gelöst werden müssen, beispielsweise im Rahmen von Schnittebenenverfahren, Branch-and-Bound oder Branch-and-Cut.
In der Praxis hängt die Laufzeit des Simplex-Verfahren oft im wesentlichen linear von der Anzahl der Zeilen ab. Tatsächlich zeigten Borgwardt und andere in den 1980er Jahren, dass solche Fälle wie der Klee-Minty-Würfel extrem selten sind und dass einige Varianten des Simplex-Algorithmus unter bestimmten Annahmen an den Input im Mittel nur polynomiale Laufzeit benötigen. Es ist aber bis heute unklar, ob es eine Variante mit polynomialer Laufzeit für alle Instanzen gibt.

Geschichte

Die Grundlagen der linearen Optimierung wurden 1939 von dem russischen Mathematiker Leonid Witaljewitsch Kantorowitsch in seinem Buch "Mathematische Methoden in der Organisation und Planung der Produktion" gelegt. Kurz danach präsentierte der Amerikaner F.L. Hitchcock eine Arbeit zu einem Transportproblem. Im Jahre 1947 veröffentlichte George Dantzig das Simplex-Verfahren, mit dem lineare Programme erstmals systematisch gelöst werden konnten. Eine der ersten dokumentierten Anwendungen der neuen Methode war das Diäten-Problem von G.J. Stigler, dessen Ziel eine möglichst kostengünstigste Nahrungszusammensetzung für Soldaten war, die bestimmte Mindest- und Höchstmengen an Vitaminen und anderen Inhaltsstoffen erfüllte. An der optimalen Lösung dieses linearen Programms mit neun Ungleichungen und 77 Variablen waren damals neun Personen beschäftigt, die zusammen etwa 120 Manntage Rechenarbeit benötigten.Robert Bixby: Solving real-world linear programs: A decade and more of progress. In: Operations Research, Band 50, Nr. 1, 2002, S. 3-15. Interesse an dieser Arbeit zeigte zunächst das amerikanische Militär, speziell die US Air Force, die militärische Einsätze optimieren wollte. In den Folgejahren entwickelten John von Neumann und Oskar Morgenstern das Verfahren weiter.
Mit dem Aufkommen von Computern Mitte der 1950er Jahre konnte man auch größere Probleme lösen. Man entwickelte spezielle Varianten der Simplexmethode wie das revidierte Simplex-Verfahren, das sehr sparsam mit dem damals knappen und teuren Hauptspeicher umging. Im Jahre 1954 brachte William Orchard-Hays die erste kommerzielle Implementierung dieses Verfahrens auf den Markt. Im selben Jahr veröffentlichten Lemke und Beale das duale Simplex-Verfahren, das sich heute - nach weiteren Verbesserungen - zu einer der Standardmethoden zur Lösung linearer Programme entwickelt hat.
Die theoretische Komplexität des Simplex-Verfahrens war lange Zeit unklar. Erst im Jahre 1972 konstruierten V. Klee und G.J. Minty ein Beispiel, bei dem der Algorithmus alle exponentiell vielen Ecken eines Polyeders abläuft, und zeigten damit die exponentielle Laufzeit des Verfahrens. Ähnliche Beispiele wurden bisher für alle bekannten Varianten des Verfahrens gefunden.
Ab den 1970er Jahren profitierte der Simplex-Algorithmus - wie auch andere Verfahren der Linearen Optimierung - von algorithmischen Fortschritten der numerischen linearen Algebra, insbesondere bei der Lösung großer linearer Gleichungssysteme. Vor allem die Entwicklung numerisch stabiler LR-Zerlegungen für dünnbesetzte Matrizen trugen maßgeblich zum Erfolg und der Verbreitung des Simplex-Verfahrens bei.
Seit Mitte der 1970er bis Anfang der 1990er Jahre wurde das Verfahren durch die Entwicklung neuer Pivotstrategien deutlich verbessert. Vor allem die wachsende Bedeutung der ganzzahligen linearen Optimierung in den 1980er Jahren sowie die Entwicklung des dual steepest edge pricing in der Implementierung von Forrest und Goldfarb (1992) machten das duale Simplex-Verfahren zum ernsthaften Konkurrenten für andere Lösungsmethoden. Umgekehrt hatte diese Verbesserung des dualen Simplex-Algorithmus einen maßgeblichen Anteil am Erfolg von Schnittebenenverfahren und Branch-and-Cut zur Lösung ganzzahliger linearer Programme. Darüber hinaus sorgten neue Preprocessing-Methoden in den 1990er Jahren dafür, dass immer größere LPs gelöst werden konnten. Unter der - in praktischen Anwendungen fast immer erfüllten - Voraussetzung, dass die auftretenden LP-Matrizen dünnbesetzt sind, können heute lineare Programme mit mehreren Hunderttausend Variablen oder Ungleichungen innerhalb weniger Stunden optimal gelöst werden.
 
 

Ich stimme mit der Mathematik nicht überein. Ich meine, daß die Summe von Nullen eine gefährliche Zahl ist.

Stanislaw Jerzy Lec

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Simplex-Verfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Lineare Optimierung