scipy.optimize.

milp#

scipy.optimize.milp(c, *, integrality=None, bounds=None, constraints=None, options=None)[Quelle]#

Gemischt-ganzzahlige lineare Programmierung

Löst Probleme der folgenden Form

\[\begin{split}\min_x \ & c^T x \\ \mbox{so dass} \ & b_l \leq A x \leq b_u,\\ & l \leq x \leq u, \\ & x_i \in \mathbb{Z}, i \in X_i\end{split}\]

wobei \(x\) ein Vektor von Entscheidungsvariablen ist; \(c\), \(b_l\), \(b_u\), \(l\) und \(u\) Vektoren sind; \(A\) eine Matrix ist und \(X_i\) die Menge der Indizes von Entscheidungsvariablen ist, die ganzzahlig sein müssen. (In diesem Zusammenhang wird eine Variable, die nur ganzzahlige Werte annehmen kann, als "ganzzahlig" bezeichnet; sie hat eine "Ganzzahligkeits"-Beschränkung.)

Alternativ, das heißt

minimieren

c @ x

so dass

b_l <= A @ x <= b_u
l <= x <= u
Specified elements of x must be integers

Standardmäßig ist l = 0 und u = np.inf, es sei denn, dies wird mit bounds angegeben.

Parameter:

c1D dichte array_like

Die Koeffizienten der zu minimierenden linearen Zielfunktion. c wird vor der Lösung des Problems in ein Array mit doppelter Genauigkeit umgewandelt.

integrality1D dichte array_like, 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. integrality wird vor der Lösung des Problems in ein Array von Ganzzahlen umgewandelt.

boundsscipy.optimize.Bounds, optional

Grenzen für die Entscheidungsvariablen. Untere und obere Grenzen werden vor der Lösung des Problems in Arrays mit doppelter Genauigkeit umgewandelt. Der Parameter keep_feasible des Bounds-Objekts wird ignoriert. Wenn nicht angegeben, sind alle Entscheidungsvariablen auf nicht-negativ beschränkt.

constraintsSequenz von scipy.optimize.LinearConstraint, optional

Lineare Nebenbedingungen des Optimierungsproblems. Argumente können eines der folgenden sein

Ein einzelnes LinearConstraint-Objekt
Ein einzelnes Tupel, das als LinearConstraint(*constraints) in ein LinearConstraint-Objekt umgewandelt werden kann
Eine Sequenz, die vollständig aus Objekten der Typen 1 und 2 besteht.

Vor der Lösung des Problems werden alle Werte in doppelte Genauigkeit umgewandelt, und die Matrizen der Nebenbedingungskoeffizienten werden in Instanzen von scipy.sparse.csc_array umgewandelt. Der Parameter keep_feasible von LinearConstraint-Objekten wird ignoriert.

optionsdict, optional

Ein Wörterbuch von Solver-Optionen. Die folgenden Schlüssel werden erkannt.

dispbool (Standard: False): Auf True setzen, wenn Optimierungsstatusanzeigen während der Optimierung auf der Konsole ausgegeben werden sollen.
node_limitint, optional: Die maximale Anzahl von Knoten (linearen Programm-Relaxationen), die gelöst werden, bevor gestoppt wird. Standard ist keine maximale Anzahl von Knoten.
presolvebool (Standard: True): Presolve versucht, triviale Unzulänglichkeiten zu identifizieren, triviale Unbeschränktheit zu identifizieren und das Problem zu vereinfachen, bevor es an den Haupt-Solver übergeben wird.
time_limitfloat, optional: Die maximale Anzahl von Sekunden, die für die Lösung des Problems zur Verfügung stehen. Standard ist kein Zeitlimit.
mip_rel_gapfloat, optional: Abbruchkriterium für MIP-Solver: Der Solver wird beendet, wenn die Lücke zwischen dem primalen Zielfunktionswert und der dualen Zielschranke, skaliert durch den primalen Zielfunktionswert, kleiner oder gleich mip_rel_gap ist.

Rückgabe:

resOptimizeResult

Eine Instanz von scipy.optimize.OptimizeResult. Das Objekt hat garantiert die folgenden Attribute.

statusint

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

0 : Optimale Lösung gefunden.

1 : Iterations- oder Zeitlimit erreicht.

2 : Problem ist unzulänglich.

3 : Problem ist unbeschränkt.

4 : Sonstiges; siehe Nachricht für Details.

successbool

True, wenn eine optimale Lösung gefunden wurde, und False andernfalls.

messagestr

Eine Zeichenkette, die den Beendigungsstatus des Algorithmus beschreibt.

Die folgenden Attribute werden ebenfalls vorhanden sein, aber die Werte können None sein, abhängig vom Lösungsstatus.

xndarray: Die Werte der Entscheidungsvariablen, die die Zielfunktion minimieren und gleichzeitig die Nebenbedingungen erfüllen.
funfloat: Der optimale Wert der Zielfunktion c @ x.
mip_node_countint: Die Anzahl der Teilprobleme oder "Knoten", die vom MILP-Solver gelöst wurden.
mip_dual_boundfloat: Die endgültige Schätzung des unteren Grenzwerts für die optimale Lösung durch den MILP-Solver.
mip_gapfloat: Die Differenz zwischen dem primalen Zielfunktionswert und der dualen Zielschranke, skaliert durch den primalen Zielfunktionswert.

Hinweise

milp ist ein Wrapper der HiGHS-Software für lineare Optimierung [1]. Der Algorithmus ist deterministisch und findet typischerweise das globale Optimum von mäßig schwierigen gemischt-ganzzahligen linearen Programmen (wenn es existiert).

Referenzen

[1]

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

[2]

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 Problem unter https://en.wikipedia.org/wiki/Integer_programming#Example, das als Maximierungsproblem mit zwei Variablen ausgedrückt wird. Da milp erfordert, dass das Problem als Minimierungsproblem ausgedrückt wird, sind die Koeffizienten der Zielfunktion für die Entscheidungsvariablen

>>> import numpy as np
>>> c = -np.array([0, 1])

Beachten Sie das negative Vorzeichen: Wir maximieren die ursprüngliche Zielfunktion, indem wir das Negative der Zielfunktion minimieren.

Wir sammeln die Koeffizienten der Nebenbedingungen in Arrays wie

>>> A = np.array([[-1, 1], [3, 2], [2, 3]])
>>> b_u = np.array([1, 12, 12])
>>> b_l = np.full_like(b_u, -np.inf, dtype=float)

Da es keine untere Grenze für diese Nebenbedingungen gibt, haben wir eine Variable b_l mit Werten definiert, die negative Unendlichkeit darstellen. Dies ist für Benutzer von scipy.optimize.linprog, das nur "kleiner als" (oder "obere Schranke") Ungleichheitsbedingungen der Form A_ub @ x <= b_u akzeptiert, möglicherweise ungewohnt. Indem sowohl b_l als auch b_u für Nebenbedingungen b_l <= A_ub @ x <= b_u akzeptiert werden, erleichtert milp die prägnante Angabe von "größer als" Ungleichheitsbedingungen, "kleiner als" Ungleichheitsbedingungen und Gleichheitsbedingungen.

Diese Arrays werden in einem einzigen LinearConstraint-Objekt wie folgt gesammelt

>>> from scipy.optimize import LinearConstraint
>>> constraints = LinearConstraint(A, b_l, b_u)

Die Nicht-Negativitätsgrenzen für die Entscheidungsvariablen werden standardmäßig erzwungen, daher müssen wir kein Argument für bounds angeben.

Schließlich besagt das Problem, dass beide Entscheidungsvariablen ganzzahlig sein müssen

>>> integrality = np.ones_like(c)

Wir lösen das Problem wie

>>> from scipy.optimize import milp
>>> res = milp(c=c, constraints=constraints, integrality=integrality)
>>> res.x
[2.0, 2.0]

Beachten Sie, dass wir, wenn wir das relaxierte Problem (ohne Ganzzahligkeitsbeschränkungen) gelöst hätten

>>> res = milp(c=c, constraints=constraints)  # OR:
>>> # from scipy.optimize import linprog; res = linprog(c, A, b_u)
>>> res.x
[1.8, 2.8]

hätten wir nicht die korrekte Lösung durch Runden auf die nächste Ganzzahl erhalten.

Weitere Beispiele finden Sie im Tutorial.