scipy.optimize.

linprog#

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=(0, None), method='highs', callback=None, options=None, x0=None, integrality=None)[Quelle]#

Lineare Programmierung: Minimieren einer linearen Zielfunktion unter linearen Gleichheits- und Ungleichheitsnebenbedingungen.

Lineare Programmierung löst Probleme der folgenden Form

\[\begin{split}\min_x \ & c^T x \\ \mbox{so dass} \ & A_{ub} x \leq b_{ub},\\ & A_{eq} x = b_{eq},\\ & l \leq x \leq u ,\end{split}\]

wobei \(x\) ein Vektor von Entscheidungsvariablen ist; \(c\), \(b_{ub}\), \(b_{eq}\), \(l\) und \(u\) Vektoren sind; und \(A_{ub}\) und \(A_{eq}\) Matrizen sind.

Alternativ, das heißt

minimieren
```
c @ x
```

so dass

A_ub @ x <= b_ub
A_eq @ x == b_eq
lb <= x <= ub

Beachten Sie, dass standardmäßig lb = 0 und ub = None gelten. Andere Grenzen können mit bounds angegeben werden.

Parameter:

c1-D-Array

Die Koeffizienten der linearen Zielfunktion, die minimiert werden soll.

A_ub2-D-Array, optional

Die Matrix der Ungleichheitsbedingungen. Jede Zeile von A_ub gibt die Koeffizienten einer linearen Ungleichheitsbedingung für x an.

b_ub1-D-Array, optional

Der Vektor der Ungleichheitsbedingungen. Jedes Element stellt eine Obergrenze für den entsprechenden Wert von A_ub @ x dar.

A_eq2-D-Array, optional

Die Matrix der Gleichheitsbedingungen. Jede Zeile von A_eq gibt die Koeffizienten einer linearen Gleichheitsbedingung für x an.

b_eq1-D-Array, optional

Der Vektor der Gleichheitsbedingungen. Jedes Element von A_eq @ x muss gleich dem entsprechenden Element von b_eq sein.

boundsSequenz, optional

Eine Sequenz von (min, max)-Paaren für jedes Element in x, die das Minimum und Maximum dieser Entscheidungsvariable definieren. Wenn ein einzelnes Tupel (min, max) angegeben wird, gelten min und max als Grenzen für alle Entscheidungsvariablen. Verwenden Sie None, um anzuzeigen, dass keine Grenze existiert. Zum Beispiel bedeutet die Standardgrenze (0, None), dass alle Entscheidungsvariablen nicht-negativ sind, und das Paar (None, None) bedeutet keine Grenzen überhaupt, d. h. alle Variablen können beliebige reelle Zahlen sein.

methodstr, optional

Der Algorithmus, der zum Lösen des Problems in Standardform verwendet wird. Die folgenden sind unterstützt.

Die Legacy-Methoden sind veraltet und werden in SciPy 1.11.0 entfernt.

callbackcallable, optional

Wenn eine Callback-Funktion angegeben wird, wird sie mindestens einmal pro Iteration des Algorithmus aufgerufen. Die Callback-Funktion muss eine einzelne scipy.optimize.OptimizeResult mit den folgenden Feldern akzeptieren

x1-D-Array

Der aktuelle Lösungsvektor.

funfloat

Der aktuelle Wert der Zielfunktion c @ x.

successbool

True, wenn der Algorithmus erfolgreich beendet wurde.

slack1-D-Array

Die (nominal positiven) Werte des Schlupfes, b_ub - A_ub @ x.

con1-D-Array

Die (nominal nullen) Residuen der Gleichheitsbedingungen, b_eq - A_eq @ x.

phaseint

Die Phase des ausgeführten Algorithmus.

statusint

Eine Ganzzahl, die den Status des Algorithmus darstellt.

0 : Optimierung verläuft normal.

1 : Iterationslimit erreicht.

2 : Problem scheint unzulässig zu sein.

3 : Problem scheint unbeschränkt zu sein.

4 : Numerische Schwierigkeiten aufgetreten.

nitint

Die aktuelle Iterationsnummer.

messagestr

Ein String-Deskriptor des Algorithmusstatus.

Callback-Funktionen werden derzeit von den HiGHS-Methoden nicht unterstützt.

optionsdict, optional

Ein Wörterbuch von Solver-Optionen. Alle Methoden akzeptieren die folgenden Optionen

maxiterint: Maximale Anzahl von durchzuführenden Iterationen. Standard: siehe methodenspezifische Dokumentation.
dispbool: Auf True setzen, um Konvergenz-Meldungen auszugeben. Standard: False.
presolvebool: Auf False setzen, um das automatische Presolve zu deaktivieren. Standard: True.

Alle Methoden außer den HiGHS-Solvern akzeptieren auch

tolfloat

Eine Toleranz, die bestimmt, wann ein Residuum „nahe genug“ an Null ist, um als exakt Null betrachtet zu werden.

autoscalebool

Auf True setzen, um eine automatische Skalierung (Äquilibrierung) durchzuführen. Erwägen Sie die Verwendung dieser Option, wenn die numerischen Werte in den Nebenbedingungen um mehrere Größenordnungen voneinander abweichen. Standard: False.

rrbool

Auf False setzen, um die automatische Entfernung redundanter Zeilen zu deaktivieren. Standard: True.

rr_methodstring

Methode zur Identifizierung und Entfernung redundanter Zeilen aus der Gleichheitsnebenbedingungsmatrix nach dem Presolve. Für Probleme mit dichten Eingaben sind die verfügbaren Methoden zur Entfernung von Redundanzen:

SVD:: Führt wiederholt eine Singulärwertzerlegung (SVD) der Matrix durch und erkennt redundante Zeilen anhand von Nicht-Null-Werten in den linken Singulärvektoren, die zu Null-Singulärwerten korrespondieren. Kann schnell sein, wenn die Matrix nahezu vollen Rang hat.
pivot:: Verwendet den in [5] dargestellten Algorithmus, um redundante Zeilen zu identifizieren.
ID:: Verwendet eine randomisierte interpolative Zerlegung. Identifiziert Spalten der transponierten Matrix, die nicht in einer interpolativen Zerlegung der Matrix mit vollem Rang verwendet werden.
None:: Verwendet svd, wenn die Matrix nahezu vollen Rang hat, d. h. der Unterschied zwischen dem Rang der Matrix und der Anzahl der Zeilen kleiner als fünf ist. Andernfalls wird pivot verwendet. Das Verhalten dieses Standards kann sich ohne vorherige Ankündigung ändern.

Standard: None. Für Probleme mit dünnen Eingaben wird diese Option ignoriert, und der in [5] dargestellte Pivot-basierte Algorithmus wird verwendet.

Für methodenspezifische Optionen siehe show_options('linprog').

x01D-Array, optional

Schätzwerte für die Entscheidungsvariablen, die vom Optimierungsalgorithmus verfeinert werden. Dieses Argument wird derzeit nur von der Methode „revised simplex“ verwendet und kann nur verwendet werden, wenn x0 eine zulässige Basislösung darstellt.

integrality1D-Array oder int, optional

Gibt den Typ der Ganzzahligkeitsbeschränkung für jede Entscheidungsvariable an.

0 : Kontinuierliche Variable; keine Ganzzahligkeitsbeschränkung.

1 : Ganzzahlige Variable; die Entscheidungsvariable muss eine ganze Zahl innerhalb der bounds sein.

2 : Semi-kontinuierliche Variable; die Entscheidungsvariable muss innerhalb der bounds liegen oder den Wert 0 annehmen.

3 : Semi-ganzzahlige Variable; die Entscheidungsvariable muss eine ganze Zahl innerhalb der bounds sein oder den Wert 0 annehmen.

Standardmäßig sind alle Variablen kontinuierlich.

Für gemischte ganzzahlige Nebenbedingungen liefern Sie ein Array der Form c.shape. Um eine Nebenbedingung für jede Entscheidungsvariable aus kürzeren Eingaben abzuleiten, wird das Argument mit numpy.broadcast_to auf c.shape übertragen.

Dieses Argument wird derzeit nur von der Methode „highs“ verwendet und ansonsten ignoriert.

Rückgabe:

resOptimizeResult

Ein scipy.optimize.OptimizeResult, bestehend aus den folgenden Feldern. Beachten Sie, dass die Rückgabetypen der Felder davon abhängen können, ob die Optimierung erfolgreich war, daher wird empfohlen, OptimizeResult.status zu überprüfen, bevor Sie sich auf die anderen Felder verlassen.

x1-D-Array

Die Werte der Entscheidungsvariablen, die die Zielfunktion minimieren und gleichzeitig die Bedingungen erfüllen.

funfloat

Der optimale Wert der Zielfunktion c @ x.

slack1-D-Array

Die (nominal positiven) Werte der Schlupfvariablen, b_ub - A_ub @ x.

con1-D-Array

Die (nominal nullen) Residuen der Gleichheitsbedingungen, b_eq - A_eq @ x.

successbool

True, wenn der Algorithmus erfolgreich eine optimale Lösung findet.

statusint

Eine Ganzzahl, die den Exit-Status des Algorithmus darstellt.

0 : Optimierung erfolgreich abgeschlossen.

1 : Iterationslimit erreicht.

2 : Problem scheint unzulässig zu sein.

3 : Problem scheint unbeschränkt zu sein.

4 : Numerische Schwierigkeiten aufgetreten.

nitint

Die Gesamtzahl der Iterationen in allen Phasen.

messagestr

Eine Zeichenkette, die den Beendigungsstatus des Algorithmus beschreibt.

Siehe auch

show_options: Zusätzliche Optionen, die von den Solvern akzeptiert werden.

Hinweise

Dieser Abschnitt beschreibt die verfügbaren Solver, die über den Parameter ‚method‘ ausgewählt werden können.

„highs-ds“ und „highs-ipm“ sind Schnittstellen zu den HiGHS Simplex- und Interior-Point-Methoden-Solvern [13]. „highs“ (Standard) wählt automatisch zwischen den beiden. Dies sind die schnellsten linearen Programmierungs-Solver in SciPy, insbesondere für große, dünne Probleme; welcher der beiden schneller ist, hängt vom Problem ab. Die anderen Solver sind Legacy-Methoden und werden entfernt, wenn callback von den HiGHS-Methoden unterstützt wird.

Die Methode „highs-ds“ ist eine Wrapper-Implementierung der C++ High-Performance Dual Revised Simplex-Implementierung (HSOL) [13], [14]. Die Methode „highs-ipm“ ist eine Wrapper-Implementierung einer C++-Implementierung einer **I**nterior-**P**oint-**M**ethode [13]; sie verfügt über eine Crossover-Routine, so dass sie genauso genau ist wie ein Simplex-Solver. Die Methode „highs“ wählt automatisch zwischen den beiden. Für neuen Code, der linprog verwendet, empfehlen wir die explizite Auswahl einer dieser drei Methodenoptionen.

Hinzugefügt in Version 1.6.0.

Die Methode „interior-point“ verwendet den primär-dualen Pfadfolge-Algorithmus, wie in [4] beschrieben. Dieser Algorithmus unterstützt dünne Nebedingungsmatrizen und ist typischerweise schneller als die Simplex-Methoden, insbesondere für große, dünne Probleme. Beachten Sie jedoch, dass die zurückgegebene Lösung möglicherweise etwas weniger genau ist als die der Simplex-Methoden und im Allgemeinen nicht mit einer Ecke des durch die Nebenbedingungen definierten Polytope übereinstimmt.

Hinzugefügt in Version 1.0.0.

Die Methode „revised simplex“ verwendet die überarbeitete Simplex-Methode, wie in [9] beschrieben, mit dem Unterschied, dass eine Faktorisierung [11] der Basis-Matrix anstelle ihrer Inversen effizient aufrechterhalten und verwendet wird, um die linearen Systeme in jeder Iteration des Algorithmus zu lösen.

Hinzugefügt in Version 1.3.0.

Die Methode „simplex“ verwendet eine traditionelle, Full-Tableau-Implementierung von Dantzig's Simplex-Algorithmus [1], [2] (nicht das Nelder-Mead-Simplex). Dieser Algorithmus ist aus Gründen der Abwärtskompatibilität und zu Lehrzwecken enthalten.

Hinzugefügt in Version 0.15.0.

Bevor „interior-point“, „revised simplex“ oder „simplex“ angewendet werden, versucht ein Presolve-Verfahren, das auf [8] basiert, triviale Unzulässigkeiten, triviale Unbeschränktheiten und potenzielle Vereinfachungen des Problems zu identifizieren. Insbesondere prüft es auf

Nullzeilen in A_eq oder A_ub, die triviale Nebenbedingungen darstellen;
Nullspalten in A_eq und A_ub, die unbeschränkte Variablen darstellen;
Spalten-Singletons in A_eq, die feste Variablen darstellen; und
Spalten-Singletons in A_ub, die einfache Grenzen darstellen.

Wenn Presolve ergibt, dass das Problem unbeschränkt ist (z. B. eine unbeschränkte und unbeschränkte Variable mit negativem Kostenfaktor hat) oder unzulässig ist (z. B. eine Nullzeile in A_eq entspricht einem Nicht-Null-Wert in b_eq), terminiert der Solver mit dem entsprechenden Statuscode. Beachten Sie, dass Presolve abbricht, sobald ein Anzeichen von Unbeschränktheit erkannt wird; folglich kann ein Problem als unbeschränkt gemeldet werden, wenn das Problem tatsächlich unzulässig ist (aber die Unzulässigkeit noch nicht erkannt wurde). Wenn es also wichtig ist zu wissen, ob das Problem tatsächlich unzulässig ist, lösen Sie das Problem erneut mit der Option presolve=False.

Wenn weder Unzulässigkeit noch Unbeschränktheit in einem einzigen Durchlauf des Presolve erkannt werden, werden die Grenzen, wo möglich, verschärft und feste Variablen aus dem Problem entfernt. Anschließend werden linear abhängige Zeilen der Matrix A_eq entfernt (sofern sie keine Unzulässigkeit darstellen), um numerische Schwierigkeiten in der primären Lösungsroutine zu vermeiden. Beachten Sie, dass Zeilen, die nahezu linear abhängig sind (innerhalb einer vorgegebenen Toleranz), ebenfalls entfernt werden können, was in seltenen Fällen die optimale Lösung ändern kann. Wenn dies ein Problem darstellt, eliminieren Sie Redundanz aus Ihrer Problemformulierung und führen Sie die Ausführung mit der Option rr=False oder presolve=False durch.

Hier können mehrere potenzielle Verbesserungen vorgenommen werden: zusätzliche Presolve-Prüfungen, die in [8] beschrieben sind, sollten implementiert werden; das Presolve-Verfahren sollte mehrmals ausgeführt werden (bis keine weiteren Vereinfachungen vorgenommen werden können); und weitere der Effizienzverbesserungen aus [5] sollten in den Routinen zur Entfernung von Redundanz implementiert werden.

Nach dem Presolve wird das Problem in Standardform transformiert, indem die (verschärften) einfachen Grenzen in obere Schranken-Nebenbedingungen umgewandelt, nicht-negative Schlupfvariablen für Ungleichheitsnebenbedingungen eingeführt und unbeschränkte Variablen als Differenz zwischen zwei nicht-negativen Variablen ausgedrückt werden. Optional wird das Problem automatisch durch Äquilibrierung skaliert [12]. Der ausgewählte Algorithmus löst das Problem in Standardform, und eine Nachbearbeitungsroutine konvertiert das Ergebnis in eine Lösung für das ursprüngliche Problem.

Referenzen

[1]

Dantzig, George B., Linear programming and extensions. Rand Corporation Research Study Princeton Univ. Press, Princeton, NJ, 1963

[2]

Hillier, S.H. and Lieberman, G.J. (1995), „Introduction to Mathematical Programming“, McGraw-Hill, Chapter 4.

[3]

Bland, Robert G. New finite pivoting rules for the simplex method. Mathematics of Operations Research (2), 1977: pp. 103-107.

[4]

Andersen, Erling D., and Knud D. Andersen. „The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm.“ High performance optimization. Springer US, 2000. 197-232.

[5] (1,2,3)

Andersen, Erling D. „Finding all linearly dependent rows in large-scale linear programming.“ Optimization Methods and Software 6.3 (1995): 219-227.

[6]

Freund, Robert M. „Primal-Dual Interior-Point Methods for Linear Programming based on Newton’s Method.“ Unpublished Course Notes, March 2004. Available 2/25/2017 at https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec14_int_pt_mthd.pdf

[7]

Fourer, Robert. „Solving Linear Programs by Interior-Point Methods.“ Unpublished Course Notes, August 26, 2005. Available 2/25/2017 at http://www.4er.org/CourseNotes/Book%20B/B-III.pdf

[8] (1,2)

Andersen, Erling D., and Knud D. Andersen. „Presolving in linear programming.“ Mathematical Programming 71.2 (1995): 221-245.

[9]

Bertsimas, Dimitris, und J. Tsitsiklis. „Introduction to linear programming.“ Athena Scientific 1 (1997): 997.

[10]

Andersen, Erling D., et al. Implementation of interior point methods for large scale linear programming. HEC/Universite de Geneve, 1996.

[11]

Bartels, Richard H. „A stabilization of the simplex method.“ Journal in Numerische Mathematik 16.5 (1971): 414-434.

[12]

Tomlin, J. A. „On scaling linear programming problems.“ Mathematical Programming Study 4 (1975): 146-166.

[13] (1,2,3)

Huangfu, Q., Galabova, I., Feldmeier, M., und Hall, J. A. J. „HiGHS - high performance software for linear optimization.“ https://highs.dev/

[14]

Huangfu, Q. und Hall, J. A. J. „Parallelizing the dual revised simplex method.“ Mathematical Programming Computation, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

Beispiele

Betrachten Sie das folgende Problem

\[\begin{split}\min_{x_0, x_1} \ -x_0 + 4x_1 & \\ \mbox{so dass} \ -3x_0 + x_1 & \leq 6,\\ -x_0 - 2x_1 & \geq -4,\\ x_1 & \geq -3.\end{split}\]

Das Problem ist nicht in dem von linprog akzeptierten Format dargestellt. Dies ist leicht zu beheben, indem die Ungleichheitsbedingung „größer als“ in eine Ungleichheitsbedingung „kleiner als“ umgewandelt wird, indem beide Seiten mit einem Faktor von \(-1\) multipliziert werden. Beachten Sie auch, dass die letzte Bedingung eigentlich die einfache Grenze \(-3 \leq x_1 \leq \infty\) ist. Schließlich müssen wir, da es keine Grenzen für \(x_0\) gibt, explizit die Grenzen \(-\infty \leq x_0 \leq \infty\) angeben, da standardmäßig Variablen nicht-negativ sind. Nach dem Sammeln der Koeffizienten in Arrays und Tupeln sind die Eingaben für dieses Problem

>>> from scipy.optimize import linprog
>>> c = [-1, 4]
>>> A = [[-3, 1], [1, 2]]
>>> b = [6, 4]
>>> x0_bounds = (None, None)
>>> x1_bounds = (-3, None)
>>> res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds])
>>> res.fun
-22.0
>>> res.x
array([10., -3.])
>>> res.message
'Optimization terminated successfully. (HiGHS Status 7: Optimal)'

Die Marginalwerte (auch Dualwerte / Schattenpreise / Lagrange-Multiplikatoren) und Residuen (Schlupfvariablen) sind ebenfalls verfügbar.

>>> res.ineqlin
  residual: [ 3.900e+01  0.000e+00]
 marginals: [-0.000e+00 -1.000e+00]

Da beispielsweise der Marginalwert, der der zweiten Ungleichheitsbedingung zugeordnet ist, -1 beträgt, erwarten wir, dass der optimale Wert der Zielfunktion um eps abnimmt, wenn wir zur rechten Seite der zweiten Ungleichheitsbedingung einen kleinen Betrag eps hinzufügen.

>>> eps = 0.05
>>> b[1] += eps
>>> linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds]).fun
-22.05

Da das Residuum der ersten Ungleichheitsbedingung 39 beträgt, können wir die rechte Seite der ersten Bedingung um 39 verringern, ohne die optimale Lösung zu beeinträchtigen.

>>> b = [6, 4]  # reset to original values
>>> b[0] -= 39
>>> linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds]).fun
-22.0