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

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

Ein Sudoku

Gesucht ist eine Formulierung des Sudoku-Spiels als Optimierungsmodell. Seien zunächst $R=\{1,\ldots ,9\}$ und $C=\{1,\ldots ,9\}$ die Menge der Zeilen bzw. Spalten des Sudokus und $B\ =\ {\big \{}\{(3i+k,3j+l)|\ k,l\in \{1,2,3\}|\ i,j\in \{0,1,2\}\}{\big \}}$ 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 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

Ein intuitiver Ansatz wäre es, für jedes Sudoku-Feld eine ganzzahlige Entscheidungsvariable $x_{rc}\in \{1,\ldots ,9\}$ einzuführen, welche angibt, welche Zahl in das Feld $(r,c),\ r\in R,\ c\in C,$ der Reihe $r$ und Spalte $c$ einzutragen sind. So würde etwa $x_{2,4}=5$ 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 $x_{1,1}=5,\ x_{1,2}=3,\ \ldots ,\ x_{9,9}=9$ 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 $x_{rc}$ und $x_{r'c'}$ unterscheiden sich genau dann, wenn gilt $|x_{rc}-x_{r'c'}|\ \geq \ 1$, wobei hier sehr viele Kombinationen von Indexpaaren $(r,c)$ und $(r',c')$ 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 $a_{rcr'c'}$ 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 $r\in R$, Spalte $c\in C$ und Wert $v\in V:=\{1,\ldots ,9\}$ keine beliebige ganzzahlige, sondern eine binäre Entscheidungsvariable $y_{rcv}\in \{0,1\},\ r\in R,\ c\in C,\ v\in V$ mit folgender Interpretation ein. Falls $y_{rcv}=1$ gilt, steht der Wert $v$ in Zeile $r$ und Spalte $c$ und für ${\textstyle y_{rcv}=0}$ nicht. Beispielsweise bedeutet ${\textstyle y_{2,4,5}=1}$, 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 ${\textstyle \sum _{r\in R}y_{rcv}=1}$ für alle Spalten $c\in C$ und Werte $v\in V$ 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 $\sum _{v\in V}y_{rcv}\ =\ 1$ 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 $\theta :\mathbb {R} \to \mathbb {R}$ eine streng monoton steigende Funktion ist, kann sie auf eine Zielfunktion angewandt werden, ohne die Lage der Optimalpunkte zu verändern. Beispiele:

• Die Optimierungsmodelle $\min _{a,b}{\sqrt {\sum _{i=1}^{N}(a^{T}x^{i}+b-y_{i})^{2}}}$ und $\min _{a,b}\sum _{i=1}^{N}(a^{T}x^{i}+b-y_{i})^{2}$ besitzen dieselben Optimalpunkte $(a^{\star },b^{\star })$, 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 $\ell _{2}$-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 $x\cdot y$ zweier binärer Entscheidungsvariablen ${\textstyle y,z\in \{0,1\}}$ kann linear umformuliert werden, indem es durch zusätzliche kontinuierliche Variable $a\in [0,1]$ substituiert wird und das Produkt durch die drei Ungleichungen

$$y\geq a,\quad z\geq a,\quad y+z-1\leq a$$

ersetzt wird. Per Fallunterscheidungen kann gezeigt werden, dass sich durch obige Formulierung $a$ genauso verhält, wie das Produkt $x\cdot y$, nämlich null ist, sollte eine der beiden Variablen verschwinden und genau dann eins ist, wenn $x=y=1$ gilt.

Produkt einer Binärvariable und einer kontinuierlichen Variable

Die nichtlineare Gleichung $xy\ =\ a$ kann auch linear umformuliert werden, wenn ${\textstyle y\in \{0,1\}}$ gilt und $x\in [L,U]\subset \mathbb {R}$ für zwei reelle Zahlen $L\leq U$. In diesem Fall ist der Ausdruck äquivalent zu

$Ly\ \leq \ a\ \leq \ Uy,\quad x-(1-y)U\ \leq \ a\ \leq x-(1-y)L$,

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 $|x|\leq a$ leicht durch die äquivalenten beiden linearen Ungleichungen $x\leq a,\ -x\leq a$ ersetzt werden kann, gestaltet es sich für $|x|\geq a$ etwas komplexer. Da $|x|\geq a$ äquivalent zur logischen Oder-Aussage $x\geq a$ oder $x\leq -a$ 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

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. 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. Langristigere Entscheidungen wie etwa optimale Standortplanungen für neue Standorte sind Teil von strategischen Optimierungsmodellen.

Art der IT-Lösung

Ein Optimierungsmodell wird in der Regel in bestehende IT-Infrastruktur eingebettet, wobei mindestens folgende Typen zu unterscheiden sind.

One-Shot-Solution

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.

Stand-Alone-Solution

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.

Fully-Flegded-Solution

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.

Weiterführende Literatur

Bü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/