Ein Optimierungsmodell ist ein mathematisches Modell, welches einen zu optimierenden Sachverhalt beschreibt und aus Daten, Entscheidungsvariablen, einer Zielfunktion und einer zulässigen Menge besteht.
Abgrenzung zu Optimierungsproblem 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. So gibt es etwa viele Optimierungsmodelle, die das Problem des Handlungsreisenden darstellen, die jeweils unterschiedliche Vor- und Nachteile haben.
Ziele guter Modellierung 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
das zu lösende Anwendungsproblem mit ausreichend hoher Genauigkeit zu beschreiben und ein Optimierungsmodell zu erstellen, welches anschließend mit der zur Verfügung stehenden Software und Rechenleistung ausreichend schnell gelöst werden kann.
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.
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. 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.
Beispiele für gute und schlechte Modellierung mini|Ein SudokuGesucht 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. Zunächst werden die Pakete itertools und Python-MIP importiert. Letzteres kann mit dem freien Open-Source Solver CBC („COIN-OR Branch-and-Cut“) oder mit dem kommerziellen Solver Gurobi verwendet werden.from itertools import combinations from mip import BINARY, CBC, GUROBI, INTEGER, ModelAnschließ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 schlechtes Sudoku-Modell 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("+-------+-------+-------+")
Ein gutes Sudoku-Modell 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("+-------+-------+-------+")
Weitere Beispiele Für die folgenden Probleme existieren jeweils zahlreiche Optimierungsmodelle, die sich in der Regel jeweils nicht klar dominieren. Das Unit-Commitment-Problem (Kraftwerkseinsatzoptimierung) Das Problem des Handlungsreisenden, insbesondere auch die ganzzahligen Formulierungen auf der englischsprachigen Wikipedia-Seite Zahlreiche Probleme in der chemischen Industrie, der Produktionswirtschaft, Transportwesen, Finanzen, Agrarindustrie, Gesundheitswesen, Personalplanung, Lebensmittelindustrie, Papierindustrie, Supply-Chain-Management, Statistik und Machine Learning
Modellierungstricks 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.
Streng monotone Transformationen
Falls eine streng monoton steigende Funktion ist, kann sie auf eine Zielfunktion angewandt werden, ohne die Lage der Optimalpunkte zu verändern. Beispiele:
Die Optimierungsmodelle und besitzen dieselben Optimalpunkte , da das zweite Problem aus erstem durch Quadrieren der Zielfunktion hervorging und das Quadrieren auf allen nichtnegativen Zahlen eine streng monotone Transformation darstellt. Das Problem entspricht dem Minimieren der -Norm des Vorhersagefehlers und ist ein häufig auftretendes Problem in der Statistik (s. Methode der kleinsten Quadrate). Bei der Berechnung des Maximum-Likelihood-Schätzers der Exponentialverteilung wird statt der Likelihood-Funktion die sogenannte Log-Likelihood-Funktion minimiert, da sich hier der Maximalpunkt leichter berechnen lässt und das Logarithmieren nichtnegativer Zahlen ebenfalls eine streng monotone Transformation ist.
Lineare Umformulierung von Produkten Produkte zweier Variablen lassen sich linear äquivalent umformulieren, falls mindestens eine der beiden Variablen eine Binärvariable ist.
Produkt zweier Binärvariablen 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.
Produkt einer Binärvariable und einer kontinuierlichen Variable 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.
Lineare Umformulierung von Beträgen 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.
Planungsebenen in der Praxis Für den erfolgreichen Einsatz von Optimierungsmodellen in der Praxis sollte die zeitliche Einordnung sowie die Einbindung in die IT-Infrastruktur beachtet werden.
Zeitlicher Planungshorizont