Aufgrund persönlicher Erfahrungen würde ich sagen, dass Simplex-Methoden nur unwesentlich einfacher zu implementieren sind als Interior-Point-Methoden, basierend auf persönlicher Erfahrung aus der Implementierung sowohl von Primal-Simplex- als auch von Basic-Interior-Point-Methoden in MATLAB im Rahmen einer linearen Programmierklasse . Die Haupthindernisse bei Primal Simplex sind die korrekte Implementierung von Phase I und Phase II sowie die korrekte Implementierung einer Antiradfahrregel. Die Haupthindernisse bei der Implementierung einer Innenpunktmethode für die lineare Programmierung sind in der Regel die korrekte Implementierung der iterativen Methode und die entsprechende Skalierung des Barriereparameters.
Eine ausführlichere Beschreibung der Vor- und Nachteile der einzelnen Algorithmen finden Sie in einem Lehrbuch zur linearen Programmierung, z. B. Einführung in die lineare Optimierung von Bertsimas und Tsitsiklis. ( Haftungsausschluss: Ich habe die lineare Programmierung aus diesem Lehrbuch gelernt und habe die lineare Programmierung am MIT von Bertsimas 'Frau übernommen.) Hier sind einige der Grundlagen:
Vorteile von Simplex:
- Gegeben Entscheidungsvariablen, gewöhnlich konvergiert in Operationen mit schwenkt.nO ( n )O ( n )
- Nützt die Geometrie des Problems aus: besucht Scheitelpunkte einer möglichen Menge und prüft jeden besuchten Scheitelpunkt auf Optimalität. (Bei Primal Simplex können die reduzierten Kosten für diese Prüfung verwendet werden.)
- Gut für kleine Probleme.
Nachteile von Simplex:
- Mit Entscheidungsvariablen können Sie immer eine Probleminstanz finden, bei der der Algorithmus -Operationen und Pivots benötigt, um eine Lösung zu finden.nO ( 2n)
- Nicht so toll für große Probleme, da Schwenkvorgänge teuer werden. Schnittflächenalgorithmen oder Algorithmen zur verzögerten Spaltengenerierung wie Dantzig-Wolfe können diesen Mangel manchmal ausgleichen.
Vorteile der Innenpunktmethoden:
- Haben Sie eine asymptotische Polynomzeitkomplexität von , wobei die Anzahl der in den Algorithmus eingegebenen Bits ist.O ( n3.5L2LogL logLogL )L
- Besser für große, spärliche Probleme, da die für den Algorithmus erforderliche lineare Algebra schneller ist.
Nachteile der inneren Punktmethoden:
- Es ist nicht so intuitiv befriedigend, weil Sie Recht haben. Diese Methoden besuchen keine Eckpunkte. Sie wandern durch die Innenregion und suchen nach einer Lösung, wenn sie erfolgreich sind.
- Bei kleinen Problemen ist Simplex wahrscheinlich schneller. (Sie können pathologische Fälle wie den Klee-Minty-Würfel konstruieren.)