Optimierungsmodell
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
BearbeitenDie 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]
Ziele guter Modellierung
BearbeitenDas 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.[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]
Beispiele für gute und schlechte Modellierung
BearbeitenGesucht 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 („COIN-OR Branch-and-Cut“) 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)
]
Eine schlechtes Sudoku-Modell
BearbeitenEin 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
BearbeitenAlternativ 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
BearbeitenFür die folgenden Probleme existieren jeweils zahlreiche Optimierungsmodelle, die sich in der Regel jeweils nicht klar dominieren.
- Das Unit-Commitment-Problem (Kraftwerkseinsatzoptimierung)[8]
- Das Problem des Handlungsreisenden[2], 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[9][3][10][1]
Modellierungstricks
BearbeitenDie 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]
Streng monotone Transformationen
BearbeitenFalls 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
BearbeitenProdukte zweier Variablen lassen sich linear äquivalent umformulieren, falls mindestens eine der beiden Variablen eine Binärvariable ist.
Produkt zweier Binärvariablen
BearbeitenDas 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
BearbeitenDie 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
BearbeitenWä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
BearbeitenFür den erfolgreichen Einsatz von Optimierungsmodellen in der Praxis sollte die zeitliche Einordnung sowie die Einbindung in die IT-Infrastruktur beachtet werden.[1]
Zeitlicher Planungshorizont
BearbeitenOptimierungsmodelle 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]
Art der IT-Lösung
BearbeitenEin Optimierungsmodell wird in der Regel in bestehende IT-Infrastruktur eingebettet, wobei mindestens folgende Typen zu unterscheiden sind.[1]
One-Shot-Solution
BearbeitenEin 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.
Stand-Alone-Solution
BearbeitenWird 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.
Fully-Flegded-Solution
BearbeitenIst 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.
Weiterführende Literatur
BearbeitenBücher:
- J. Kallrath: Gemischt-ganzzahlige Optimierung: Modellierung in der Praxis, 2. Auflage. Springer Spektrum, Berlin, Heidelberg, 2013, ISBN 978-3-658-00689-1
- N. Sudermann-Merx: Einführung in Optimierungsmodelle. Springer Spektrum, Berlin, Heidelberg, 2023, ISBN 978-3-662-67380-5.
- H. P. Williams: Model Building in Mathematical Programming, 5. Auflage. John Wiley & Sons, Hoboken, New Jersey 2020, ISBN 978-1-118-44333-0.
Blogs/Weblinks:
- E. Kalvelagen: https://yetanothermathprogrammingconsultant.blogspot.com/
- T. Hürlimann: https://matmod.ch/
Einzelnachweise
Bearbeiten- ↑ a b c d e f Nathan Georg Sudermann-Merx: Einführung in Optimierungsmodelle: mit Beispielen und Real-World-Anwendungen in Python. Springer Spektrum, Berlin / Heidelberg 2023, ISBN 978-3-662-67380-5.
- ↑ a b David L. Applegate, Robert E. Bixby, Vašek Chvatál, William J. Cook: The traveling salesman problem: a computational study (= Princeton series in applied mathematics). Princeton university press, Princeton (N.J.) 2006, ISBN 978-0-691-12993-8.
- ↑ a b c Josef Kallrath: Gemischt-ganzzahlige Optimierung: Modellierung in der Praxis (= Lehrbuch). 2., überarbeitete und erweiterte Auflage. Springer Spektrum, Wiesbaden 2013, ISBN 978-3-658-00689-1.
- ↑ Tobias Achterberg, Robert E. Bixby, Zonghao Gu, Edward Rothberg, Dieter Weninger: Presolve Reductions in Mixed Integer Programming. In: INFORMS Journal on Computing. Band 32, Nr. 2, April 2020, ISSN 1091-9856, S. 473–506, doi:10.1287/ijoc.2018.0857 (kobv.de [PDF; abgerufen am 29. Dezember 2023]).
- ↑ Laurence A. Wolsey: Integer programming. 2. Auflage. Wiley, Hoboken, NJ Chichester, West Sussex 2021, ISBN 978-1-119-60653-6.
- ↑ intro_opt_models/code/chapter_5_MILP/sudoku at main · spiralulam/intro_opt_models. Abgerufen am 29. Dezember 2023 (englisch).
- ↑ Python-MIP. Abgerufen am 29. Dezember 2023.
- ↑ Bernard Knueven, James Ostrowski, Jean-Paul Watson: On Mixed-Integer Programming Formulations for the Unit Commitment Problem. In: INFORMS Journal on Computing. 25. Juni 2020, ISSN 1091-9856, doi:10.1287/ijoc.2019.0944 (optimization-online.org [PDF; abgerufen am 30. Dezember 2023]).
- ↑ a b Hilary P. Williams: Model building in mathematical programming. 5. Auflage. John Wiley & Sons Ltd, Chichester 2013, ISBN 978-1-118-44333-0 (researchgate.net [abgerufen am 30. Dezember 2023]).
- ↑ Yet Another Math Programming Consultant. Abgerufen am 30. Dezember 2023 (englisch).
- ↑ Christodoulos A. Floudas, Xiaoxia Lin: Mixed Integer Linear Programming in Process Scheduling: Modeling, Algorithms, and Applications. In: Annals of Operations Research. Band 139, Nr. 1, Oktober 2005, ISSN 0254-5330, S. 131–162, doi:10.1007/s10479-005-3446-x (umich.edu [PDF; abgerufen am 30. Dezember 2023]).
- ↑ Nazanin Shabani, Taraneh Sowlati: A mixed integer non-linear programming model for tactical value chain optimization of a wood biomass power plant. In: Applied Energy. Band 104, April 2013, ISSN 0306-2619, S. 353–361, doi:10.1016/j.apenergy.2012.11.013.
- ↑ Hong Yan, Zhenxin Yu, T.C. Edwin Cheng: A strategic model for supply chain design with logical constraints: formulation and solution. In: Computers & Operations Research. Band 30, Nr. 14, Dezember 2003, ISSN 0305-0548, S. 2135–2155, doi:10.1016/s0305-0548(02)00127-2.