Was ist die Obergrenze für den Simplex-Algorithmus, um eine Lösung für ein lineares Programm zu finden?
Wie würde ich vorgehen, um einen Beweis für einen solchen Fall zu finden? Es scheint, als ob der schlimmste Fall ist, wenn jeder Eckpunkt besucht werden muss, dass es . In der Praxis wird der Simplex-Algorithmus jedoch bei Standardproblemen erheblich schneller ausgeführt.
Wie kann ich über die durchschnittliche Komplexität eines Problems nachdenken, das mit dieser Methode gelöst wird?
Alle Informationen oder Referenzen werden sehr geschätzt!
Antworten:
Der Simplex-Algorithmus besucht im schlimmsten Fall tatsächlich alle2n Eckpunkte ( Klee & Minty 1972 ), und dies stellt sich für jede deterministische Pivot-Regel als wahr heraus. In einer wegweisenden Arbeit mit einer geglätteten Analyse haben Spielman und Teng (2001) jedoch bewiesen, dass die erwartete Laufzeit des Simplex-Algorithmus für alle Eingaben polynomisch ist, wenn die Eingaben in den Algorithmus leicht zufällig gestört werden Bei jedem Problem handelt es sich um ein "naheliegendes" Problem, das mit der Simplex-Methode effizient gelöst werden kann. Es deckt praktisch jedes lineare Programm ab, das Sie lösen möchten. Anschließend stellten Kelner und Spielman (2006) vor Ein Simplex-Algorithmus mit Polynom-Zeit-Randomisierung, der alle Eingaben verarbeitet, auch die schlechten für den ursprünglichen Simplex-Algorithmus.
quelle
Wie Lev sagte, besucht der Algorithmus im schlimmsten Fall alle2d Ecken wo d ist die Anzahl der Variablen. Die Leistung des Simplex-Algorithmus kann jedoch auch stark von der verwendeten Pivot-Regel abhängen. Soweit mir bekannt ist, ist noch offen, ob es eine bestimmte deterministische Pivotregel mit subexponentieller Worst-Case-Laufzeit gibt. Viele Kandidaten wurden durch niedrigere Ergebnisse ausgeschlossen. Kürzlich zeigten Friedmann, Hansen und Zwick auch die ersten nicht-polynomialen Untergrenzen für einige natürliche randomisierte Pivot-Regeln mit einigen später bereitgestellten Korrekturen .
However, adding to the smoothed analysis result mentioned by Lev: Following Spielman and Tengs seminal paper introducing smoothed analysis, Vershynin improved their bounds further in 2006. He showed that the expected running time on slightly perturbed instances is only poly-logarithmic in the number of constraintsn , down from n86 .
quelle
To obtain insight into the worst-case and average-case analysis of the simplex method, you should read "Smoothed Analysis: Why The Simplex Algorithm Usually Takes Polynomial Time." by Spielman and Teng.
quelle
A good reference on why simplex is not running in polynomial time, rather than why it's exponential is Papadimitriou & Steiglitz Combinatorial Optimization, Section 8.6 in which they demonstrate that Simplex is not a polynomial-time algorithm.
quelle
2019 löst der OpenSource-LP-Löser GLPK das Klee-Minty-Cube- ProblemD = 200
In weniger als 100 Millisekunden auf einem 2,7-GHz-iMac:
Kann jemand andere Möglichkeiten vorschlagen, um schwierige Probleme für die Simplex-Methode zu konstruieren, die langsam, aber nicht speichergebunden sind?
Hinzugefügt: Lateinische Quadrate oder 3D-Permutationsmatrizen scheinen viele Eckpunkte zu haben - wie viele?
Theorie und Praxis sind in der Theorie näher als in der Praxis.
quelle
Der ursprüngliche Simplex-Algorithmus kann abweichen. es wird in bestimmten Fällen wiederholt. Daher keine allgemeine Bindung. Andere Antworten geben Ihnen Antworten auf die verschiedenen Modifikationen des Simplex-Algorithmus.
quelle