Loading AI tools
Aus Wikipedia, der freien Enzyklopädie
Ein Optimierungsmodell ist ein mathematisches Modell, welches einen zu optimierenden Sachverhalt beschreibt und aus Daten, Entscheidungsvariablen, einer Zielfunktion und einer zulässigen Menge besteht.
Die Abgrenzung eines Optimierungsmodells zu einem Optimierungsproblem wird in der Literatur nicht trennscharf vollzogen. Bei einem Optimierungsmodell liegt jedoch der Schwerpunkt auf der Modellbildung, da es in der Regel zahlreiche Möglichkeiten gibt, ein Anwendungsproblem zu modellieren und die Modellierung selbst ein Schritt ist, der bestmöglich vollzogen werden sollte.[1] So gibt es etwa viele Optimierungsmodelle, die das Problem des Handlungsreisenden darstellen, die jeweils unterschiedliche Vor- und Nachteile haben.[2]
Das Ergebnis der Modellbildung in der mathematischen Optimierung ist ein Optimierungsmodell. Dieses wird anschließend von einem Solver gelöst, welcher eine optimale Lösung des Optimierungsmodells berechnet und damit eine Lösung des zugrundeliegenden Problems bereitstellt. Um aus Anwendungssicht ein zufriedenstellendes Ergebnis zu erreichen, sind die Ziele guter Modellierung demzufolge
Weitere Ziele sind etwa die Lesbarkeit der mathematischen Formulierung oder die Wiederverwertbarkeit der Implementierung.
Ob das Optimierungsmodell den Anwendungsfall ausreichend genau beschreibt, stellt sich in der Regel durch eine Diskussion der Ergebnisse mit den jeweiligen Anwenderinnen heraus. Dies ist in der Regel ein iterativer Prozess, weshalb frühzeitig Feedback eingeholt werden sollte.[3]
Die Auswirkungen verschiedener Modellierungsvarianten auf die Laufzeit des Solvers sind a priori oft schwer einzuschätzen, was unter anderem daran liegt, das kommerzielle Solver-Implementierungen nicht offen einsehbar sind und etwa durch umfangreiche Presolve-Techniken Umformulierungen der ursprünglichen Formulierung durchführen werden[4]. Grundsätzlich gibt es in der gemischt-ganzzahligen Optimierung einen Trade-Off zwischen möglichst engen (eng. tight) Formulierungen – d. h. ganzzahligen Formulierungen, deren kontinuierliche Relaxierung die konvexe Hülle der zulässigen Punkte möglichst eng einschließt – und kompakten Formulierungen, d. h. Modellen mit möglichst wenigen Variablen und Nebenbedingungen. Diese beiden Ziele sind in der Regel konfliktär, da etwa durch die Einführung zusätzlicher Nebenbedingungen (auch Cuts) engere Formulierungen erreicht werden können.[5]
Gesucht ist eine Formulierung des Sudoku-Spiels als Optimierungsmodell. Seien zunächst und die Menge der Zeilen bzw. Spalten des Sudokus und die Menge der 3x3-Boxen. Da hier lediglich eine zulässige Lösung gesucht ist, spielt die Zielfunktion keine Rolle. Es gibt nun verschiedene Möglichkeiten, mit der Modellierung fortzufahren. Die dargestellten Varianten sind der Literatur entnommen und auch die zugehörigen Python-Codes sind online verfügbar.[1][6] Zunächst werden die Pakete itertools und Python-MIP[7] importiert. Letzteres kann mit dem freien Open-Source Solver CBC oder mit dem kommerziellen Solver Gurobi verwendet werden.
from itertools import combinations
from mip import BINARY, CBC, GUROBI, INTEGER, Model
Anschließend wird der Solver gewählt, die initialen Werte des Sudokus übergeben und die Zeilen, Spalten und Boxen definiert. Das Dictionary init_vals
wird je nach Sudoku mit den Werten befüllt, die bereits in das Sudokufeld eingetragen wurden.
# Choose CBC or Gurobi
solver_name = CBC
# Todo: provide initial values in the format (r, c): v
init_vals = {}
# Needed data structures
rows = range(1, 10)
columns = range(1, 10)
boxes = [
[
(3 * i + k, 3 * j + l)
for k in range(1, 4)
for l in range(1, 4)
]
for i in range(3)
for j in range(3)
]
Ein intuitiver Ansatz wäre es, für jedes Sudoku-Feld eine ganzzahlige Entscheidungsvariable einzuführen, welche angibt, welche Zahl in das Feld der Reihe und Spalte einzutragen sind. So würde etwa bedeuten, dass in der zweiten Zeile und vierten Spalte die Zahl fünf eingetragen wird.
Bei den Nebenbedingungen werden nun im Beispiel des nebenstehenden Sudokus zunächst mit alle Variablen fixiert, für die bereits Zahlen in die entsprechenden Felder wurden.
Außerdem sollen sich die Einträge pro Zeile, Spalte und Box unterscheiden. Die Variablen und unterscheiden sich genau dann, wenn gilt , wobei hier sehr viele Kombinationen von Indexpaaren und untersucht werden müssen. Für kommerzielle Solver kann diese nichtlineare Nebenbedingung genau so formuliert werden. Für Open-Source-Frameworks müsste diese Constraint unter Einführung vieler Hilfsvariablen weiter umformuliert werden.
Hier ist die zugehörige Python-Implementierung.
# Model declaration
m = Model("Sudoku integer", solver_name=solver_name)
# Decision variables
x = {
(r, c): m.add_var(var_type=INTEGER, lb=1, ub=9)
for r in rows
for c in columns
}
y = {
(r, c, r1, c1): m.add_var(var_type=BINARY)
for r in rows
for c in columns
for r1 in rows
for c1 in columns
}
# Constraints
# Respect initial values
for ((r, c), v) in init_vals.items():
m += x[r, c] == v
# Unique value per row
for r in rows:
for (c, c1) in combinations(columns, 2):
m += x[r, c] + 1 <= x[r, c1] + y[r, c, r, c1] * 9
m += x[r, c] >= x[r, c1] + 1 - (1 - y[r, c, r, c1]) * 9
# Unique value per column
for c in columns:
for (r, r1) in combinations(rows, 2):
m += x[r, c] + 1 <= x[r1, c] + y[r, c, r1, c] * 9
m += x[r, c] >= x[r1, c] + 1 - (1 - y[r, c, r1, c]) * 9
# Unique value per box
for box in boxes:
for ((r, c), (r1, c1)) in combinations(box, 2):
m += x[r, c] + 1 <= x[r1, c1] + y[r, c, r1, c1] * 9
m += x[r, c] >= x[r1, c1] + 1 - (1 - y[r, c, r1, c1]) * 9
# Optimize statement
m.optimize()
Das resultierende Sudoku kann anschließend ausgegeben werden. Man beachte, dass obige Formulierung nur mit Gurobi in angemessener Zeit lösbar ist.
# Print solution
for r in rows:
if (r - 1) % 3 == 0:
print("+-------+-------+-------+")
line = ""
for c in columns:
if (c - 1) % 3 == 0:
line += "| "
line += f"{int(x[r, c].x)} "
if c == 9:
line += "|"
print(line)
print("+-------+-------+-------+")
Alternativ kann ein Ansatz gewählt werden, der im Data Science unter dem Begriff One-Hot Encoding bekannt ist. Es wird für jede Kombination aus Zeile , Spalte und Wert keine beliebige ganzzahlige, sondern eine binäre Entscheidungsvariable mit folgender Interpretation ein. Falls gilt, steht der Wert in Zeile und Spalte und für nicht. Beispielsweise bedeutet , dass in der zweiten Zeile und vierten Spalte der Wert fünf eingetragen wird. Dass etwa pro Spalte jeder Wert nur ein Mal vorkommen darf, wird über für alle Spalten und Werte modelliert, da eine Summe von Binärvariablen genau dann eins ist, wenn eine der Binärvariablen eins und alle verbleibenden null sind. Die Bedingungen pro Zeile und Box können analog formuliert werden. Es ist nicht zu vergessen, dass in jedes Feld überhaupt ein Wert einzutragen ist, was über erzwungen wird.
# Model declaration
m = Model("Sudoku binary", solver_name=solver_name)
# Decision variables
y = {
(r, c, v): m.add_var(var_type=BINARY)
for r in rows
for c in columns
for v in values
}
# Constraints
# Respect initial values
for ((r, c), v) in init_vals.items():
m += y[r, c, v] == 1
# One entry per cell
for r in rows:
for c in columns:
m += xsum(y[r, c, v] for v in values) == 1
# Unique value per row
for r in rows:
for v in values:
m += xsum(y[r, c, v] for c in columns) == 1
# Unique value per column
for c in columns:
for v in values:
m += xsum(y[r, c, v] for r in rows) == 1
# Unique value per box
for box in boxes:
for v in values:
m += xsum(y[r, c, v] for (r, c) in box) == 1
# Optimize statement
m.optimize()
Im Gegensatz zu obiger Formulierung kann diese auch von CBC innerhalb weniger Sekunden gelöst werden.
# Print solution
for r in rows:
if (r - 1) % 3 == 0:
print("+-------+-------+-------+")
line = ""
for c in columns:
if (c - 1) % 3 == 0:
line += "| "
val = int(sum(y[r, c, v].x * v for v in values))
line += f"{val} "
if c == 9:
line += "|"
print(line)
print("+-------+-------+-------+")
Für die folgenden Probleme existieren jeweils zahlreiche Optimierungsmodelle, die sich in der Regel jeweils nicht klar dominieren.
Die folgenden Modellierungstricks ermöglichen es, Ausdrücke (hoffentlich) vorteilhaft umzuformulieren, um eine bessere Solver-Laufzeit zu erreichen. Es handelt sich hierbei um einfache Tricks. Für fortgeschrittene Tricks wie die approximative Linearisierung oder das Modellieren mit Lazy Constraints und Callback-Funktionen sei auf die weiterführende Literatur verwiesen.[3][1][9]
Falls eine streng monoton steigende Funktion ist, kann sie auf eine Zielfunktion angewandt werden, ohne die Lage der Optimalpunkte zu verändern. Beispiele:
Produkte zweier Variablen lassen sich linear äquivalent umformulieren, falls mindestens eine der beiden Variablen eine Binärvariable ist.
Das Produkt zweier binärer Entscheidungsvariablen kann linear umformuliert werden, indem es durch zusätzliche kontinuierliche Variable substituiert wird und das Produkt durch die drei Ungleichungen
ersetzt wird. Per Fallunterscheidungen kann gezeigt werden, dass sich durch obige Formulierung genauso verhält, wie das Produkt , nämlich null ist, sollte eine der beiden Variablen verschwinden und genau dann eins ist, wenn gilt.
Die nichtlineare Gleichung kann auch linear umformuliert werden, wenn gilt und für zwei reelle Zahlen . In diesem Fall ist der Ausdruck äquivalent zu
,
was ähnlich zum obigen rein binären Fall wieder per Fallunterscheidung verifiziert werden kann.
Während die stückweise lineare Gleichung leicht durch die äquivalenten beiden linearen Ungleichungen ersetzt werden kann, gestaltet es sich für etwas komplexer. Da äquivalent zur logischen Oder-Aussage oder ist, wird dies durch die Einführung einer Binärvariable modelliert, was ausführlicher in der Literatur oder in dem Artikel zur gemischt-ganzzahligen Optimierung nachgelesen werden kann.
Für den erfolgreichen Einsatz von Optimierungsmodellen in der Praxis sollte die zeitliche Einordnung sowie die Einbindung in die IT-Infrastruktur beachtet werden.[1]
Optimierungsmodelle können in der operativen, taktischen oder strategischen Planung eingesetzt werden. Im operativen Geschäft müssen kurzfristig optimale Entscheidungen gefällt werden, wobei der Planungshorizont in der Regel deutlich unter einem Jahr bis hin zu wenigen Stunden oder Minuten liegen kann. Beispiele hierfür sind Optimierungsmodelle in der Produktion, die konkrete Belegungspläne für produzierende Maschinen berechnen.[11] Die taktische Planung bezieht sich in der Regel auf wenige Jahre und versucht etwa optimale Entscheidungen in Bezug auf die Wertschöpfungskette eines Unternehmens zu treffen.[12] Langristigere Entscheidungen wie etwa optimale Standortplanungen für neue Standorte sind Teil von strategischen Optimierungsmodellen.[13]
Ein Optimierungsmodell wird in der Regel in bestehende IT-Infrastruktur eingebettet, wobei mindestens folgende Typen zu unterscheiden sind.[1]
Ein Optimierungsmodell, welches als One-Shot-Solution eingesetzt wird, berechnet optimale Lösungen für selten oder unregelmäßig anfallende Aufgaben, deren einmalige Lösung das Problem vorerst erschöpfend behandelt. Ein Beispiel wäre die Layout-Planung einer neu zu errichtenden Produktionshalle eines kleinen oder mittelständischen Unternehmens. Diese Fragestellung kann losgelöst von der bereits existierenden IT-Infrastruktur beantwortet und umgesetzt werden. Auch wenn die anzuwendende Methodik sehr anspruchsvoll sein kann, so ist das Problem aus IT-Sicht angenehm zu handhaben, da keine Software, sondern Ergebnisse in Form von Zahlen produziert werden.
Wird ein Optimierungsmodell als Stand-Alone-Solution eingesetzt, so wird darunter ein selbstständiges Stück Software verstanden, in dem Optimierungskomponenten integriert sind, das jedoch IT-seitig eher losgelöst von der bestehenden Infrastruktur funktioniert. Ein Beispiel dafür wäre ein Jupyter Notebook oder eine Web-Applikation, deren Daten in Form von CSV-Dateien zur Verfügung gestellt werden. Das Ergebnis ist ein Tool, das, vergleichbar zu Excel-Dateien, zur Verfügung steht, um damit Analysen durchzuführen. Der Datenfluss ist jedoch nicht vollständig automatisiert, sodass sich diese Art von Lösung für wiederkehrende Aufgaben niedriger Frequenz eventuell anbieten kann.
Ist ein Optimierungsmodell Teil einer Fully-Flegded-Solution, so handelt es sich dabei um eine vollständig integrierte Lösung, die automatisiert Daten erhält und produziert. Aufgrund des hohen Automatisierungsgrades sind in der Regel viele Pre- und Postprocessing-Schritte notwendig, um ein hohes Sicherheitslevel garantieren zu können. Dies resultiert idealerweise in einem hochproduktiven und skalierbaren System, das auch im operativen Betrieb für einen hohen Mehrwert sorgen kann, nachdem die hohen IT-Hürden bei der Einführung des Systems und der Schulung der Nutzer gemeistert wurden.
Bücher:
Blogs/Weblinks:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.