Anhang B: Katalog der Modellierungsmuster

Wofür dieser Anhang gedacht ist: Sie sitzen vor einem konkreten Problem und wissen nicht, wie Sie eine bestimmte Regel in ein Modell bekommen. Suchen Sie hier das Muster, das zu Ihrer Formulierung passt. Jeder Eintrag nennt die Regel in Alltagssprache, die mathematische Formulierung, den Code und die Fallstricke.

Übersicht

Umgekehrte Richtung: Wer von einem Satz aus der Besprechung kommt und das Muster sucht, findet in Abschnitt 4.6 ein Lexikon, das genau so herum aufgebaut ist — und die Wendungen benennt, bei denen es keine eindeutige Übersetzung gibt.

Die Spalte „Wo im Buch“ nennt das Kapitel, in dem das Muster im Zusammenhang vorkommt — nicht die einzige Stelle, an der es taugt. Die Nummern entstehen beim Bauen; im Quelltext dieses Anhangs steht keine einzige.

Logische Schalter

B1 — Aktivierungsschalter (Fixkosten)

Regel. „Wenn überhaupt etwas produziert wird, fallen Rüstkosten F an.“

x \le M\,y,\qquad y\in\{0,1\},\ x\ge0 Zielfunktion: \dots + F\,y

modell.Add(x <= M * y)              # CP-SAT
# LP/MILP:  Zeile  x - M*y <= 0

⚠️ M so klein wie möglich — idealerweise die ohnehin vorhandene Kapazitätsgrenze von x. Zu großes M macht die LP-Relaxation wertlos (Abschnitt 6.5).

B2 — Semikontinuierliche Variable

Regel. „Entweder gar nicht oder mindestens L (und höchstens U).“

L\,y \le x \le U\,y,\qquad y\in\{0,1\}

Typisch für Mindestordergrößen, Mindestlosgrößen, Mindestabnahmemengen.

B3 — Implikation

Regel. „Wenn A gewählt wird, muss auch B gewählt werden.“

y_A \le y_B

modell.AddImplication(y_a, y_b)     # CP-SAT, gleichwertig und lesbarer

Für die Umkehrung („nur wenn“) einfach vertauschen. Für Äquivalenz: y_A = y_B.

B4 — Entweder-Oder (disjunktive Bedingung)

Regel. „Es muss f(\mathbf{x}) \le b_1 oder g(\mathbf{x}) \le b_2 gelten.“

f(\mathbf{x}) \le b_1 + M(1-y),\qquad g(\mathbf{x}) \le b_2 + M y

# CP-SAT: viel eleganter ueber Reifizierung
modell.Add(f_ausdruck <= b1).OnlyEnforceIf(y)
modell.Add(g_ausdruck <= b2).OnlyEnforceIf(y.Not())

B5 — Exklusiv-Oder

Regel. „Genau eine der Optionen wird gewählt.“

\sum_{j=1}^N y_j = 1

modell.AddExactlyOne(y)             # bzw. AddAtMostOne / AddBoolOr

B6 — Kardinalität

Regel. „Höchstens (mindestens, genau) K von N.“

\sum_j y_j \le K \qquad(\ \ge K,\ = K\ )

B7 — Bedingte Kopplung (Konjunktion)

Regel. „Wenn A und B, dann auch C.“

y_A + y_B - 1 \le y_C

Prüfen Sie die vier Fälle: nur bei y_A = y_B = 1 erzwingt die Ungleichung y_C \ge 1.

Für „Wenn A oder B, dann C“: y_A \le y_C und y_B \le y_C.

Mengen und Grenzen

B8 — Weiche Grenze mit Strafkosten

Regel. „Möglichst nicht über b — wenn doch, kostet es.“

f(\mathbf{x}) \le b + s,\qquad s \ge 0 Zielfunktion: \dots + c_{\text{Strafe}}\cdot s

Das ist das wichtigste Muster überhaupt für praxistaugliche Modelle (siehe B18).

B9 — Gestaffelte Preise (stückweise linear)

Regel. „Die ersten 100 Stück kosten 5 €, danach 8 €.“

Variablen je Stufe: x = x_1 + x_2 mit 0 \le x_1 \le 100, x_2 \ge 0; Kosten 5x_1 + 8x_2.

⚠️ Das funktioniert nur bei steigenden Preisen (konvexe Kostenfunktion) ohne Binärvariablen — der Optimierer füllt dann automatisch erst die billige Stufe. Bei fallenden Preisen (Mengenrabatt, konkav) braucht man Binärvariablen je Stufe, sonst „schummelt“ das Modell.

B10 — Absolutbetrag / Abweichung

Regel. „Die Abweichung vom Zielwert soll klein sein, egal in welche Richtung.“

|x - z| \le d \quad\Longleftrightarrow\quad x - z \le d\ \ \text{und}\ \ z - x \le d

In der Zielfunktion (Minimierung von |x-z|) genügt: \min d \quad\text{u. d. N.}\quad x-z \le d,\quad z-x \le d

turnover = cp.norm1(w - w_alt)      # CVXPY macht das automatisch

B11 — Min/Max in der Zielfunktion

Regel. „Der am schlechtesten gestellte Beteiligte soll möglichst gut dastehen“ (Maximin/Fairness).

\max t \quad\text{u. d. N.}\quad t \le f_i(\mathbf{x})\ \ \forall i

modell.AddMaxEquality(max_var, liste)   # CP-SAT
modell.AddMinEquality(min_var, liste)
# Fairness ueber die Spannweite:
modell.Add(spannweite == max_var - min_var)   # dann minimieren

B12 — Verhältnis-Bedingung

Regel. „Der Anteil von Gruppe G soll mindestens 30 % betragen.“

\frac{\sum_{i\in G} x_i}{\sum_i x_i} \ge 0{,}3 \quad\Longleftrightarrow\quad \sum_{i\in G} x_i \ge 0{,}3\sum_i x_i

⚠️ Brüche immer wegmultiplizieren — ein Quotient von Variablen ist nichtlinear und meist nicht konvex. Nach dem Umstellen ist die Bedingung linear.

B25 — Mindestabnahmemenge über einen Zeitraum

Regel. „Entweder wir arbeiten mit diesem Lieferanten gar nicht, oder wir nehmen ihm im Jahr mindestens 500 Einheiten ab.“

Ein Schalter für den ganzen Zeitraum, nicht je Periode:

Q\,y \le \sum_{t} x_{t} \le U\,y, \qquad y \in \{0,1\},\ x_t \ge 0

# y_s ist EINE Variable je Lieferant - nicht eine je Lieferant UND Periode
y = {s: modell.NewBoolVar(f"vertrag_{s}") for s in lieferanten}
for s in lieferanten:
    jahresmenge = sum(x[s, t] for t in perioden)
    modell.Add(jahresmenge >= MINDESTMENGE[s] * y[s])
    modell.Add(jahresmenge <= JAHRESKAPAZITAET[s] * y[s])   # koppelt x an y

⚠️ Die häufigste Verwechslung: L\,y_t \le x_t je Periode (B2) ist ein anderes Modell — es verlangt in jeder einzelnen Periode eine Mindestmenge und ist erheblich strenger. Wer den Jahresvertrag so formuliert, erzeugt ein unlösbares Modell und sucht den Fehler dann in den Daten.

⚠️ Die obere Kopplung nicht vergessen. Ohne \sum_t x_t \le U\,y kann das Modell y = 0 setzen und trotzdem einkaufen — der Vertrag gilt dann als nicht geschlossen, die Ware fließt aber. Das ist der Trickle Flow aus Abschnitt 6.5, nur andersherum. U ist die Jahreskapazität des Lieferanten, keine runde Zahl.

B27 — Budgetlimit

Regel. „Alle Maßnahmen zusammen dürfen 2 Mio. € nicht überschreiten.“

\sum_i c_i x_i \le B

Mit x_i \in \{0,1\} ist das ein Rucksackproblem — dasselbe Muster, das Kapitel 6 an Rucksack.py vorrechnet und Kapitel 10 als Pricing-Teilproblem wiederverwendet.

modell.Add(sum(KOSTEN[i] * x[i] for i in massnahmen) <= BUDGET)
# Mehrere Toepfe: je Topf eine Zeile - NICHT die Summe ueber alle Toepfe
for topf, grenze in BUDGETS.items():
    modell.Add(sum(KOSTEN[i] * x[i] for i in massnahmen
                   if TOPF[i] == topf) <= grenze)

💡 Der Schattenpreis des Budgets ist die Zahl, nach der die Geschäftsführung fragt: „Was bringt der nächste Euro?“ Bei einem LP (Lineare Programmierung) ist er direkt ablesbar. Bei Ganzzahligkeit gibt es ihn nicht — die Dualwerte der Relaxation sind keine gültige Antwort. Rechnen Sie stattdessen mit erhöhtem Budget neu und vergleichen Sie die Zielwerte (Abschnitt 5.9).

⚠️ Die LP-Relaxation verspricht zu viel. Sie darf die letzte Maßnahme anteilig kaufen und liefert deshalb eine Schranke, die spürbar über dem tatsächlich Erreichbaren liegen kann. Wer sie als Prognose berichtet, verspricht Geld, das nicht kommt.

Zeit und Reihenfolge

B13 — Vorrangbeziehung

Regel. „Arbeitsgang B darf erst beginnen, wenn A fertig ist.“

\text{start}_B \ge \text{ende}_A

Mit Mindestwartezeit w: \text{start}_B \ge \text{ende}_A + w.

B14 — Nichtüberlappung

Regel. „Eine Maschine bearbeitet nur einen Job gleichzeitig.“

modell.AddNoOverlap([intervall_1, intervall_2, ...])

In MILP (Gemischt-ganzzahlige Optimierung) bräuchte man je Paar eine Disjunktion (B4) — bei k Jobs sind das \binom{k}{2} Konstruktionen. Nehmen Sie hier CP-SAT.

B15 — Kumulative Ressource

Regel. „Zu keinem Zeitpunkt dürfen mehr als 3 Arbeiten gleichzeitig laufen“ bzw. „die Stromlast darf 500 kW nie übersteigen“.

modell.AddCumulative(intervalle, bedarfe, kapazitaet)

B16 — Gleitendes Fenster

Regel. „Höchstens 5 Arbeitstage in Folge“ / „mindestens 2 freie Tage je Woche“.

\sum_{u=t}^{t+5} x_u \le 5 \qquad \forall t

for t in range(len(tage) - 5):
    modell.Add(sum(x[p, u] for u in range(t, t + 6)) <= 5)

B17 — Umrüst- bzw. Wechselkosten

Regel. „Ein Produktwechsel kostet Rüstzeit.“

Hilfsvariable z_t \in \{0,1\} = „in Periode t wird gewechselt“:

z_t \ge y_{j,t} - y_{j,t-1} \qquad \forall j, t

Zielfunktion: \dots + c_{\text{Ruest}}\sum_t z_t. Für reihenfolgeabhängige Rüstzeiten: AddCircuit mit Übergangsmatrix.

B26 — Rüstzeit als Kapazitätsverbrauch

Regel. „Das Umrüsten kostet nicht nur Geld, es kostet Maschinenstunden — und die fehlen dann für die Produktion.“

B17 verbucht den Wechsel in der Zielfunktion. Sobald die Maschine ausgelastet ist, gehört er zusätzlich in die Kapazitätszeile:

\sum_j a_j\,x_{j,t} \;+\; \sum_j r_j\,y_{j,t} \;\le\; C_t \qquad \forall t

mit a_j Stückzeit, r_j Rüstzeit, y_{j,t}\in\{0,1\} = „Produkt j läuft in Periode t“ (gekoppelt über B1: x_{j,t} \le M\,y_{j,t}).

for t in perioden:
    modell.Add(sum(STUECKZEIT[j] * x[j, t] for j in produkte)
               + sum(RUESTZEIT[j] * y[j, t] for j in produkte) <= KAPAZITAET[t])

⚠️ Wer die Rüstzeit nur als Kosten führt, erhält Pläne, die in der Halle nicht laufen. Das Modell verteilt die Produktion dann auf viele kleine Lose, weil ein zusätzlicher Wechsel zwar etwas kostet, aber keine Zeit verbraucht — die Rechnung geht auf dem Papier auf und in der Schicht nicht.

Reihenfolgeabhängig (r_{ij} statt r_j — von Weiß auf Schwarz ist schneller als umgekehrt) ist es kein Kapazitätsproblem mehr, sondern ein Rundreiseproblem: AddCircuit mit der Übergangsmatrix als Kantengewicht (B24, Kapitel 7).

Robustheit und Diagnose

B18 — Schlupfvariablen gegen Unlösbarkeit

Das wichtigste Muster für den Produktivbetrieb.

Regel. „Diese Bedingung soll gelten — aber lieber ein schlechter Plan als gar keiner.“

\sum_p x_{p,s} + u_s = 1,\qquad u_s\in\{0,1\} Zielfunktion: \dots + 10\,000\cdot u_s

Die Strafe muss hoch genug sein, dass der Solver sie nur im Notfall in Kauf nimmt, aber endlich, damit es überhaupt eine Lösung gibt. Faustregel: eine Größenordnung über der Summe aller weichen Ziele.

B19 — Hierarchische Ziele (lexikografisch)

Regel. „Erst die Besetzung sicherstellen, dann die Fairness optimieren.“

Variante A — Gewichtung: Strafen um Größenordnungen staffeln (10\,000 \gg 100 \gg 1). Einfach, aber bei extremen Skalenunterschieden numerisch heikel.

Variante B — Zweistufig lösen (sauberer):

# Stufe 1: nur das Hauptziel
modell.Minimize(unbesetzte_schichten)
loeser.Solve(modell)
bestwert = loeser.ObjectiveValue()

# Stufe 2: Hauptziel fixieren, Nebenziel optimieren
modell.Add(unbesetzte_schichten <= int(bestwert))
modell.Minimize(unfairness)
loeser.Solve(modell)

B20 — Symmetriebrechung

Regel. „Drei identische Maschinen — der Solver soll nicht alle Vertauschungen durchprobieren.“

\text{start}_1 \le \text{start}_2 \le \text{start}_3 \qquad\text{bzw.}\qquad \sum_j x_{1j} \ge \sum_j x_{2j}

Ohne Symmetriebrechung durchsucht Branch-and-Bound k! gleichwertige Lösungen. Eine einzige Ordnungsbedingung kann die Laufzeit um Größenordnungen senken.

B21 — Worst-Case-Abzug (robuste Formulierung)

Regel. „Rechne nicht mit dem geschätzten Wert, sondern mit dem ungünstigsten plausiblen.“

Bei Box-Unsicherheit \mu_i \in [\hat\mu_i - \delta_i, \hat\mu_i + \delta_i] und w \ge 0: \hat{\boldsymbol{\mu}}^\top\mathbf{w} \;\longrightarrow\; \hat{\boldsymbol{\mu}}^\top\mathbf{w} - \boldsymbol{\delta}^\top\mathbf{w}

Abgestuft (Bertsimas/Sim): nur die \Gamma ungünstigsten gleichzeitig:

abzug = cp.sum_largest(cp.multiply(delta, w), Gamma)

Netzwerke

B22 — Flusserhaltung

\sum_{j:(i,j)\in E} x_{ij} - \sum_{k:(k,i)\in E} x_{ki} = b_i \qquad \forall i

b_i > 0 Quelle, b_i < 0 Senke, b_i = 0 Umschlagknoten. Voraussetzung: \sum_i b_i = 0 — sonst unlösbar (Dummy-Knoten einführen).

B23 — Zuordnung 1:1

\sum_j x_{ij} = 1\ \forall i,\qquad \sum_i x_{ij} = 1\ \forall j,\qquad x_{ij} \ge 0

💡 Ganzzahligkeit nicht fordern! Die Matrix ist total unimodular; ein LP-Solver liefert automatisch 0/1-Lösungen. Für reine Zuordnungen ist scipy.optimize.linear_sum_assignment (Ungarischer Algorithmus, O(n^3)) noch deutlich schneller.

B24 — Subtour-Eliminierung

MTZ (einfach, aber schwach): u_i - u_j + C x_{ij} \le C - d_j \qquad \forall i\ne j

Besser in der Praxis: AddCircuit in CP (Constraint Programming)-SAT (Boolean Satisfiability) oder die Routing-Bibliothek von OR-Tools.

Ein Wort zur Auswahl

Wenn mehrere Muster passen, entscheiden Sie nach dieser Reihenfolge:

1. Gibt es ein globales Constraint dafür? (AddAllDifferent, AddNoOverlap, AddCumulative, AddCircuit) → nehmen Sie es. Es propagiert stärker und ist lesbarer.
2. Kommt man ohne Big-M aus? (z. B. B3 statt B4) → ja, dann so.
3. Muss es wirklich hart sein? → sonst B8/B18.
4. Ist M so klein wie möglich? → prüfen.