linprog(method=’highs’)#

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 Ungleichheitsbeschränkungen unter Verwendung eines der HiGHS-Solver.

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‘, die automatisch zwischen ‘highs-ds’ und ‘highs-ipm’ wählt. ‘interior-point’ (Standard), ‘revised simplex’ und ‘simplex’ (veraltet) sind ebenfalls verfügbar.

integrality1D-Array oder Integer, 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 Ganzzahligkeitsbeschränkungen geben Sie ein Array der Form c.shape an. Um eine Beschränkung für jede Entscheidungsvariable aus kürzeren Eingaben abzuleiten, wird das Argument mithilfe von np.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 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-Simplex-Methode beinhaltet dies Iterationen in allen Phasen. Für die HiGHS-Interior-Point-Methode beinhaltet dies keine Crossover-Iterationen.

crossover_nitint

Die Anzahl der Primal/Dual-Schritte, die während der Crossover-Routine für die HiGHS-Interior-Point-Methode durchgeführt wurden. Dies ist 0 für die HiGHS-Simplex-Methode.

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 zu durchführenden Iterationen in jeder Phase. Für ‘highs-ipm’ beinhaltet dies nicht die Anzahl der Crossover-Iterationen. 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)

Dual-Zulässigkeitstoleranz für ‘highs-ds’. Das Minimum davon und primal_feasibility_tolerance wird für die Zulässigkeitstoleranz von ‘highs-ipm’ verwendet.

primal_feasibility_tolerancedouble (Standard: 1e-07)

Primal-Zulässigkeitstoleranz für ‘highs-ds’. Das Minimum davon und dual_feasibility_tolerance wird für die Zulässigkeitstoleranz von ‘highs-ipm’ verwendet.

ipm_optimality_tolerancedouble (Standard: 1e-08)

Optimalitätstoleranz für ‘highs-ipm’. Mindestens zulässiger Wert ist 1e-12.

simplex_dual_edge_weight_strategystr (Standard: None)

Strategie für Simplex-Dualkanten-Gewichte. Der Standardwert None wählt automatisch eine der folgenden Optionen aus.

'dantzig' verwendet Dantzig's ursprüngliche Strategie, die am negativsten reduzierten Kosten auszuwählen.

'devex' verwendet die in [15] beschriebene Strategie.

steepest verwendet die exakte steepest-edge-Strategie, wie in [16] beschrieben.

'steepest-devex' beginnt mit der exakten steepest-edge-Strategie, bis die Berechnung zu kostspielig oder ungenau wird, und wechselt dann zur devex-Methode.

Derzeit wählt None immer 'steepest-devex', dies kann sich jedoch ändern, wenn neue Optionen verfügbar werden.

mip_rel_gapdouble (Standard: None)

Abbruchkriterium für MIP-Solver: Der Solver wird beendet, wenn die Lücke zwischen dem primalen Zielfunktionswert und der dualen Zielfunktionsschranke, skaliert mit dem primalen Zielfunktionswert, kleiner oder gleich mip_rel_gap ist.

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

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

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

[15]

Harris, Paula MJ. „Pivot selection methods of the Devex LP code.“ Mathematical programming 5.1 (1973): 1-28.

[16]

Goldfarb, Donald, und John Ker Reid. „A practicable steepest-edge simplex algorithm.“ Mathematical Programming 12.1 (1977): 361-371.