Bei der Formalisierung von LP-Problemen muss man sich häufig mit Multi-Index-Variablen befassen. Bei Problemen mit großen Abmessungen ist dies offen gesagt eine häufige Sache.
Die Wechselbeziehungen solcher Multi-Index-Variablen in der Zielfunktion (lineare Form ist auch ein lineares Optimierungskriterium) und Einschränkungen (in Form von linearen Gleichungen und Ungleichungen) sollten programmgesteuert erzeugt werden. Bei der Arbeit mit PuLP (LP Library Port für Python) werden zwei Hauptansätze für eine solche Generierung verwendet:
- Matrix A (Constraint-Matrix) mit Python-Listengeneratoren explizit generieren. Zum Beispiel wie folgt : Sudoku-Problem
- Erzeugung symbolischer Variablen mit Bindung an Indizes durch Wörterbücher in impliziter Form. Dies kann manuell über ein Diktat oder über ein PuLP-Plugin erfolgen
Das klassische LP-Problem nahezu jeder Dimension kann auf jede dieser Arten leicht formalisiert werden. Wenn jedoch neue Strukturen von Einschränkungen entwickelt werden (insbesondere wenn die Logik der Wechselbeziehungen von Variablen komplizierter wird, neue Bedeutungsvariablen auftreten, werden einige Indizes aufgegeben oder neue Indizes eingeführt). Die Aggregation / Zerlegung von Gruppen von Variablen usw.) erfordert eine einfache Verfolgung von Variablen mit mehreren Indizes im Python-Programmcode selbst, was in den obigen Ansätzen direkt fehlt.
Um dieses Problem zu lösen, wird vorgeschlagen, das PuLP-MiA- Add -On zu verwenden (Link zum Repository mit einer kurzen Beschreibung der Funktionalität).
Der Autor ist weit davon entfernt zu glauben, dass dies eine Lösung für alle Probleme ist, die bei der Formalisierung und Lösung von LP-Problemen mit einer komplexen Struktur von Einschränkungen auftreten. In der langjährigen Praxis (insbesondere wenn die Änderung in langen Zeitintervallen erfolgt) hat sich der Ansatz jedoch vor allem aufgrund der folgenden Annehmlichkeiten als gut erwiesen:
- Das Erstellen / Binden an vorhandene Variablen erfolgt automatisch
- Explizite Zuordnung eines Variablennamens und seiner Indizes
- Variablenname - beliebige Zeichenfolge
- Indizes - numerische Werte
- Die Anzahl der Indizes ist bedingt unbegrenzt (möglicherweise sind überhaupt keine Indizes vorhanden).
- Die Ergebnisse der Lösung des LP-Problems werden in Form eines Wörterbuchs angezeigt, in dem die Schlüssel Multi-Index-Variablen ungleich Null sind (das Verhalten kann geändert werden).
Vielleicht ist das Addon sehr nützlich für jemanden, der sich langfristig mit Operationen befasst. MIT-Lizenz. Es wird traditionell über Pip installiert .
PS Für diejenigen, die mit dem Lesen fertig sind, wird es immer noch klein sein
Beispiel für die Bildung einer Reihe von Einschränkungen))
from itertools import product
from pulp_mia import Task, Constraint
i_set = list(range(5))
j_set = list(range(5))
m_set = list(range(2))
g_set = list(range(4))
s_set = list(range(5))
k_set = list(range(5))
task = Task(debug=True)
for i, m, g, s, k in product(i_set, m_set, g_set, s_set, k_set):
a_new = Constraint('<=')
for j in j_set:
a_new.setCoeff(('x', i, j, m, g, s, k), 1)
a_new.setBValue(1)
task.addConstraint(a_new)
print(task)
#TASK info:
# NAME: test-task
# SIZE: 5000 x 1000
(für den Rest siehe die kurze Beschreibung des Addons )
PPS ja, irgendwo tief unter der Haube lebt ein gewöhnliches Wörterbuch.