linprog(method=’highs-ipm’)#

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)

Lineare Programmierung: Minimieren einer linearen Zielfunktion unter linearen Gleichheits- und Ungleichheitsnebenbedingungen mithilfe des HiGHS-Interior-Point-Lösers.

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 gilt, es sei denn, dies wird mit bounds angegeben.

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 die minimale und maximale Wert dieser Entscheidungsvariablen definieren. Verwenden Sie None, um anzuzeigen, dass keine Grenze existiert. Standardmäßig sind die Grenzen (0, None) (alle Entscheidungsvariablen sind nicht-negativ). Wenn ein einzelnes Tupel (min, max) bereitgestellt wird, dienen min und max als Grenzen für alle Entscheidungsvariablen.
methodstr: Dies ist die Methodenspezifische Dokumentation für 'highs-ipm'. ‘highs-ipm’, ‘highs-ds’, ‘interior-point’ (Standard), ‘revised simplex’ und ‘simplex’ (veraltet) sind ebenfalls verfügbar.

Rückgabe:

resOptimizeResult

Ein scipy.optimize.OptimizeResult mit den Feldern

x1D-Array

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

funfloat

Der optimale Wert der Zielfunktion c @ x.

slack1D-Array

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

con1D-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 : Iterations- oder Zeitlimit erreicht.

2 : Problem scheint unzulässig zu sein.

3 : Problem scheint unbeschränkt zu sein.

4 : Der HiGHS-Solver hatte ein Problem.

messagestr

Eine Zeichenkette, die den Beendigungsstatus des Algorithmus beschreibt.

nitint

Die Gesamtzahl der durchgeführten Iterationen. Für die HiGHS-Interior-Point-Methode sind hierin keine Crossover-Iterationen enthalten.

crossover_nitint

Die Anzahl der während der Crossover-Routine für die HiGHS-Interior-Point-Methode durchgeführten Primär-/Dual-Verschiebungen.

ineqlinOptimizeResult

Lösungs- und Sensitivitätsinformationen für die Ungleichheitsbeschränkungen, b_ub. Ein Wörterbuch, das die Felder enthält

residualnp.ndnarray: Die (nominal positiven) Werte der Schlupfvariablen, b_ub - A_ub @ x. Diese Größe wird auch häufig als „Schlupf“ bezeichnet.
marginalsnp.ndarray: Die Sensitivität (partielle Ableitung) der Zielfunktion in Bezug auf die rechte Seite der Ungleichheitsbeschränkungen, b_ub.

eqlinOptimizeResult

Lösungs- und Sensitivitätsinformationen für die Gleichheitsbeschränkungen, b_eq. Ein Wörterbuch, das die Felder enthält

residualnp.ndarray: Die (nominal nullen) Residuen der Gleichheitsbedingungen, b_eq - A_eq @ x.
marginalsnp.ndarray: Die Sensitivität (partielle Ableitung) der Zielfunktion in Bezug auf die rechte Seite der Gleichheitsbeschränkungen, b_eq.

lower, upperOptimizeResult

Lösungs- und Sensitivitätsinformationen für die unteren und oberen Schranken für Entscheidungsvariablen, bounds.

residualnp.ndarray: Die (nominal positiven) Werte der Größe x - lb (unten) oder ub - x (oben).
marginalsnp.ndarray: Die Sensitivität (partielle Ableitung) der Zielfunktion in Bezug auf die unteren und oberen bounds.

Siehe auch

Die Dokumentation für die restlichen Parameter finden Sie unter scipy.optimize.linprog

Optionen:

——-
maxiterint: Die maximale Anzahl der in einer Phase durchzuführenden Iterationen. Für ‘highs-ipm’ sind hierin keine Crossover-Iterationen enthalten. Standard ist der größtmögliche Wert für einen int auf der Plattform.
dispbool (Standard: False): Auf True setzen, wenn Optimierungsstatusanzeigen während der Optimierung auf der Konsole ausgegeben werden sollen.
presolvebool (Standard: True): Presolve versucht, triviale Unzulässigkeiten zu identifizieren, triviale Unbeschränktheit zu erkennen und das Problem zu vereinfachen, bevor es an den Hauptlöser übergeben wird. Es wird generell empfohlen, die Standardeinstellung True beizubehalten. Setzen Sie auf False, wenn Presolve deaktiviert werden soll.
time_limitfloat: Die maximal zugelassene Zeit in Sekunden zur Lösung des Problems; Standard ist der größtmögliche Wert für ein double auf der Plattform.
dual_feasibility_tolerancedouble (Standard: 1e-07): Das Minimum aus diesem Wert und der primal_feasibility_tolerance wird als Zulässigkeitstoleranz für ‘highs-ipm’ verwendet.
primal_feasibility_tolerancedouble (Standard: 1e-07): Das Minimum aus diesem Wert und der dual_feasibility_tolerance wird als Zulässigkeitstoleranz für ‘highs-ipm’ verwendet.
ipm_optimality_tolerancedouble (Standard: 1e-08): Optimalitätstoleranz für ‘highs-ipm’. Der minimal zulässige Wert ist 1e-12.
unknown_optionsdict: Optionale Argumente, die von diesem speziellen Solver nicht verwendet werden. Wenn unknown_options nicht leer ist, wird eine Warnung ausgegeben, die alle ungenutzten Optionen auflistet.

Hinweise

Methode ‘highs-ipm’ ist ein Wrapper einer C++-Implementierung einer **i**nterior-**p**oint **m**ethode [13]; sie verfügt über eine Crossover-Routine, sodass sie so genau ist wie ein Simplex-Löser. Methode ‘highs-ds’ ist ein Wrapper der C++-Hochleistungs-Dual-Revised-Simplex-Implementierung (HSOL) [13], [14]. Methode ‘highs’ wählt automatisch zwischen den beiden. Für neuen Code, der linprog verwendet, empfehlen wir explizit die Auswahl eines dieser drei Methodenwerte anstelle von ‘interior-point’ (Standard), ‘revised simplex’ und ‘simplex’ (veraltet).

Die Ergebnis-Felder ineqlin, eqlin, lower und upper enthalten alle marginals, oder partielle Ableitungen der Zielfunktion in Bezug auf die rechte Seite jeder Beschränkung. Diese partiellen Ableitungen werden auch als „Lagrange-Multiplikatoren“, „Dualwerte“ und „Schattenpreise“ bezeichnet. Die Vorzeichenkonvention von marginals ist entgegengesetzt zu der von Lagrange-Multiplikatoren, die von vielen nichtlinearen Lösern erzeugt werden.

Referenzen

[13] (1,2)

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