Ich bin an der Implementierung von SM für LP-Aufgaben interessiert, habe jedoch von möglichen Fallstricken gehört: Cormens Buch sagt, dass es möglich ist, Eingabedaten zu haben, die eine naive Implementierung dazu bringen, sich in exponentieller Zeit zu verhalten. Ich habe auch gehört, dass naive Implementierung für eine Art von Daten Schleife kann.
Gibt es ein Buch / eine Arbeit / eine Quelle, die die Nuancen der praktischen Umsetzung von SM erklärt?
Danke im Voraus.
Antworten:
Ich empfehle nachdrücklich das Papier von Bixby, dem "Vater" von CPLEX, das sich nicht nur mit der Implementierung von Aspekten des (überarbeiteten) Simplex-Algorithmus befasst: Robert E. Bixby , Lösung realer linearer Programme: Ein Jahrzehnt und mehr Fortschritt , Operationen Research (50) 2002, 3-15 .
quelle
Der Simplex-Algorithmus ist nicht in P. CLRS enthalten. Daher heißt es, dass der Algorithmus, obwohl er in der Praxis "gut" funktioniert, aufgrund einiger Eingaben in exponentieller Zeit ausgeführt wird. Dies hängt eng mit dem Algorithmus zusammen, nicht mit seiner Implementierung: Sie werden dies unabhängig davon zu Gesicht bekommen, wie genau Sie den Algorithmus implementieren. LP ist jedoch in P. Dies wurde 1979 von Khachian bewiesen, sein Ellipsoid-Algorithmus ist jedoch nicht praktikabel. Heutzutage sind Innenpunktmethoden weit verbreitet. Die erste wurde 1984 von Karmarkar entdeckt.
Wenn Sie an praktischen Umsetzungen interessiert sind, schauen Sie sich Folgendes an:
GUROBI, das für den akademischen Gebrauch kostenlos ist, ist derzeit der beste verfügbare Optimierer (sowohl sequentielle als auch parallele Shared-Memory-Versionen):
http://www.gurobi.com
die GLPK Bibliothek:
http://www.gnu.org/software/glpk/
Dies ist ein Open-Source-Projekt, das Implementierungen für Folgendes bereitstellt:
quelle
Das Buch zur linearen Programmierung von Vanderbei geht viele der Details auf niedriger Ebene durch ... Aber wie die anderen Antworten / Kommentare andeuteten, ist die Implementierung des LP-Lösers eine schwierige und undankbare Aufgabe. Off-the-Shelf-Solver ist wahrscheinlich der richtige Weg ... (Es gibt auch einige Open-Source-LP-Solver ...)
quelle
Es sind nicht nur naive Implementierungen, die sich manchmal in exponentieller Zeit verhalten. Tatsächlich denke ich, dass alle bekannten deterministischen und randomisierten Regeln über superpolynome Worst-Case-Eingaben verfügen. Die meisten bekannten Eingaben, die dieses Worst-Case-Verhalten hervorrufen, sind stark strukturiert, eine verwandte Frage:
Die Struktur pathologischer Instanzen für Simplex-Algorithmen
In der Praxis funktioniert SM jedoch gut. Dies wurde durch die Einführung einer geglätteten Analyse formalisiert, bei der es sich im Grunde genommen um eine Worst-Case-Analyse mit leicht gestörten Eingaben handelt. Nach dieser Analyse ist SM polytime, dh für jede Eingabe (auch für die pathologischen) gibt es eine leichte Störung, die es dem Algorithmus ermöglicht, eine gute Leistung zu erbringen. Diese Erkenntnis wurde in einen randomisierten Algorithmus umgewandelt , der in Polytime arbeitet. Soweit ich weiß, wird jedoch noch diskutiert, ob dieser Algorithmus als "echter" Simplex-Algorithmus eingestuft werden kann. Ich weiß auch nicht, ob Standardpakete etwas in dieser Richtung implementieren, aber Sie sollten in der Lage sein, eine Implementierung zu finden, wenn Sie herumsuchen, da das Ergebnis 5+ Jahre alt ist.
quelle
Sie könnten Luenberger, Ye, Linear and Nonlinear Programming, 3rd ed. Das scheint ziemlich umfassend zu sein, aber ich habe es noch nicht weit genug geschafft zu sagen, ob es Ihre Frage vollständig beantwortet.
quelle