Gemischt-ganzzahlige Optimierung

In der gemischt-ganzzahligen Optimierung (englisch mixed-integer optimization oder mixed-integer programming) werden Optimierungsprobleme untersucht, die kontinuierliche und ganzzahlige Entscheidungsvariablen besitzen. Sie ist ein Teilgebiet der mathematischen Optimierung mit Anwendungen in der Automobilindustrie, Chemieindustrie, Energiewirtschaft, Finanzindustrie, Gesundheitswesen, Lebensmittelindustrie, Papierindustrie, Supply Chain Management (insbes. Transport, Logistik und Produktion), Statistik, Machine Learning und der Telekommunikation.

Mathematische Definition

Ein gemischt-ganzzahliges (nichtlineares) Optimierungsproblem (engl.: mixed-integer (nonlinear) program oder mixed-integer (nonlinear) problem, kurz: MINLP) ist ein Optimierungsproblem, welches aus einer Zielfunktion, kontinuierlichen und ganzzahligen Entscheidungsvariablen und einer zulässigen Menge besteht. Die zulässige Menge wird durch Gleichungen und Ungleichungen beschrieben, wobei untere und obere Schranken an die Entscheidungsvariablen als besonders einfach zu handhabende Nebenbedingungen oft separat aufgeführt werden. Mathematisch formuliert lautet ein MINLP mit $n\in \mathbb {N}$ Entscheidungsvariablen

${\begin{aligned}\mathrm {MINLP} :\qquad \min _{x}f(x)\quad \mathrm {s.t.} \quad &L_{i}\leq x_{i}\leq U_{i},\quad i\in \{1,\ldots ,n\}\\&g_{i}(x)\leq 0,\quad i\in I\\&h_{j}(x)=0,\quad j\in J\\&x_{i}\in \mathbb {Z} ,\quad i\in {\cal {I}}.\end{aligned}}$

Die zu minimierende Zielfunktion $f:\mathbb {R} ^{n}\to \mathbb {R}$ sowie die die Restriktionen definierenden Funktionen $g_{i}:\mathbb {R} ^{n}\to \mathbb {R}$ und $h_{j}:\mathbb {R} ^{n}\to \mathbb {R}$ dürfen beliebige nichtlineare Funktionen sein, deren stetige Differenzierbarkeit jedoch in der Literatur meistens vorausgesetzt wird. Für die Schranken an die Entscheidungsvariable $x_{i}$ gilt $L_{i}\in \mathbb {R} \cup \{-\infty \}$ bzw. $U_{i}\in \mathbb {R} \cup \{\infty \}$. In der Menge ${\cal {I}}$ sind die Indizes der ganzzahligen Variablen hinterlegt und die Mengen $I$ und $J$ dienen der Indizierung der auftretenden Ungleichungs- und Gleichungsrestriktionen. Natürlich können alle auftretenden Indexmengen auch leer sein.

Einfache Beispiele

Die folgenden Beispiele sind der Literatur entnommen.

Links: Optimalpunkt der kontinuierlichen Relaxierung, Rechts: Optimalpunkte des gemischt-ganzzahligen Problems

Minimierung über einer elliptischen gemischt-ganzzahligen zulässigen Menge

Zu lösen ist folgendes MINLP mit einer linearen Zielfunktion und nichtlinearen Nebenbedingungen sowie einer Ganzzahligkeitsbedingung an $x_{1}$, wohingegen $x_{2}$ eine kontinuierliche Entscheidungsvariable ist.

$$\max _{x}x_{1}\quad \mathrm {s.t.} \quad {\frac {(x_{1}-2)^{2}}{2.5^{2}}}+(x_{2}-1.5)^{2}\ \leq \ 1,\quad x_{1}\in \mathbb {Z}$$

Eine Minimierung auf der kontinuierlichen Relaxierung der zulässigen Menge – also der Menge die entsteht, wenn die Ganzzahligkeitsbedingung ignoriert wird – ergibt den eindeutigen Optimalpunkt $x^{\star }=(4.5,1.5)$. Wird jedoch berücksichtigt, dass $x_{1}$ ganzzahlig sein muss, so sind alle zulässigen Punkte mit $x_{1}=4$ optimal.

Gemischt-ganzzahlige Modellierung einer Menge mit disjunktiver Struktur

Gesucht ist eine gemischt-ganzzahlige Beschreibung der Menge $M\ =\ \{x\in [0,10]:\ |x-5|\geq 2\}$, die alle reellen Zahlen zwischen 0 und 10 enthält, deren Abstand zu 5 größer oder gleich 2 ist. Zunächst wird notiert, dass eine solche Zahl zwischen 0 und 3 oder zwischen 7 und 10 liegen muss. Es gilt also $M\ =\ \{x\in [0,10]:\ x\leq 3{\text{ oder }}x\geq 7\}$ und das auftretende logische Oder, das auch unter dem Namen Disjunktion bekannt ist, ist eine logische Verknüpfung. Da sich logische Verknüpfungen durch Binärvariablen modellieren lassen, wird eine solche Variable $y\in \{0,1\}$ eingeführt, um folgendes System linearer Ungleichungen zu erhalten:

$$0\leq x\leq 10-7y,\quad 7(1-y)\leq x\leq 10,\quad y\in \{0,1\}$$

Durch Fallunterscheidungen lässt sich nun überprüfen, dass das Ungleichungssystem tatsächlich äquivalent zur Menge $M$ ist. Für $y=0$ gilt $0\leq x\leq 10$ und $7\leq x\leq 10$, also insgesamt $x\in [7,10]$. Für $y=1$ hingegen reduziert sich das System zu $0\leq x\leq 3$ und $0\leq x\leq 10$, also $x\in [0,3]$.

Ausgewählte Anwendungen

• Alle kombinatorischen Optimierungsprobleme, wie etwa das Rucksackproblem, das Problem des Handlungsreisenden oder das Bin-Packing-Problem
• Zahlreiche Optimierungsprobleme in der Energiewirtschaft wie etwa die Kraftwerkseinsatzoptimierung (engl. unit commitment problem)
• Scheduling-Probleme wie etwa die Maschinenbelegungsplanung in der Produktion
• Transportlogistik, zum Beispiel das Fleet Assignment Problem in der Luftfahrtindustrie, und zahlreiche Varianten der Tourenplanung (engl. vehicle routing problem)
• Das Sparse Regression Problem, robuste Regression und andere Probleme der Statistik und des Machine Learnings

Klassifikation von gemischt-ganzzahligen Optimierungsproblemen

Je nach mathematischer Struktur unterscheidet man zwischen verschiedenen Klassen gemischt-ganzzahliger Optimierungsprobleme. Der Vollständigkeit halber sei erwähnt, dass für ${\cal {{I}=\emptyset }}$, also im Fall ohne Ganzzahligkeitsbedingungen, das MINLP zu einem kontinuierlichen nichtlinearen Optimierungsproblem (NLP) wird. Im Folgenden gelte also stets ${\cal {{I}\neq \emptyset }}$.

• Falls die Zielfunktion $f$, sowie alle die Nebenbedingungen beschreibenden Funktionen $g_{i}$ und $h_{j}$ für alle $i\in I$ und $j\in J$ linear sind, spricht man von einem gemischt-ganzzahligen linearen Optimierungsproblem (MILP oder nur MIP).
• Ein MILP ohne kontinuierliche Entscheidungsvariablen ist ein sogenanntes ganzzahliges lineares Optimierungsproblem (ILP).
• Falls $f$ und/oder beliebig viele der Nebenbedingungen beschreibenden Funktionen $g_{i}$ und $h_{j}$ quadratisch sind, spricht man von einem gemischt-ganzzahligen quadratischen Optimierungsproblem (MIQP). Manchmal wird dies in der Literatur noch weiter unterschieden, sodass Probleme mit quadratischer Zielfunktion und linearen Restriktionen als MIQP und Optimierungsprobleme mit (teilweise) quadratischen Restriktionen als MIQCP (engl.: mixed-integer quadratically constrained program) bezeichnet werden.
• Falls die Nichtlinearität eines gemischt-ganzzahligen Optimierungsproblems „schlimmer“ als quadratisch ist, so spricht man von einem MINLP (engl.: mixed-integer nonlinear program).

Gemischt-ganzzahlige lineare Optimierungsprobleme

Einführung

Gemischt-ganzzahlige lineare Optimierungsprobleme (MILP oder nur MIP) sind die wichtigsten Vertreter gemischt-ganzzahliger Optimierungsprobleme, da sich viele große Instanzen global optimal lösen lassen und es zahlreiche Anwendungsmöglichkeiten gibt. Die Bedeutung wird dadurch verstärkt, dass sich viele nichtlineare gemischt-ganzzahlige Probleme linear umformulieren oder zumindest linear approximieren lassen. Als jeweils wichtige Spezialfälle enthält die Klasse der gemischt-ganzzahligen linearen Optimierungsprobleme (MILP) die Klasse der kontinuierlichen linearen Optimierungsprobleme (LP) sowie die Klasse der ganzzahligen linearen Optimierungsprobleme (ILP).

Mathematische Definition

Die mathematische Definition eins MILPs erfolgt nun sowohl in Summenschreibweise als auch in einer Matrix-Vektor-Formulierung, da sich die Summenschreibweise in der Regel an gängigen Modellierungsframeworks orientiert, die Matrix-Vektor-Schreibweise jedoch eine kompaktere Formulierung erlaubt.

Definition in Summen-Schreibweise

Jedes MILP lässt sich in Summen-Schreibweise in folgender Form darstellen:

${\begin{aligned}\mathrm {MILP} :\qquad \max _{x}\sum _{k=1}^{n}c_{k}x_{k}\quad \mathrm {s.t.} \quad &L_{i}\leq x_{i}\leq U_{i},\quad i\in \{1,\ldots ,n\}\\&\sum _{k=1}^{n}a_{ik}x_{k}\leq b_{i},\quad i\in I\\&\sum _{k=1}^{n}d_{jk}x_{k}=e_{j},\quad j\in J\\&x_{i}\in \mathbb {Z} ,\quad i\in {\cal {I}}\end{aligned}}$

Dabei wurden die Entscheidungsvariablen wie üblich mit $x_{i}$, $i\in \{1,\ldots ,n\}$, bezeichnet und alle sonstigen Parameter bezeichnen feste reelle Zahlen.

Definition in Matrix-Vektor-Schreibweise

In Matrix-Vektor-Schreibweise gestaltet sich die Darstellung etwas übersichtlicher.

${\begin{aligned}\mathrm {MILP} :\qquad \max _{x}c^{T}x\quad \mathrm {s.t.} \quad &L\leq x\leq U,\ Ax\leq b,\ Dx=e,\\&x_{i}\in \mathbb {Z} \quad {\text{für}}\quad i\in {\cal {I}}\end{aligned}}$

Hierbei wurden die unteren und oberen Schranken $L_{i}$ und $U_{i}$ in entsprechenden Vektoren $L\in \mathbb {R} ^{n}$ und $U\in \mathbb {R} ^{n}$ untergebracht und alle sonstigen Einträge ebenfalls in Vektoren und Matrizen passender Dimension verstaut.

Beispiel

Das folgende Optimierungsproblem ist ein einfaches Beispiel für ein MILP.

${\begin{aligned}\max _{x}x_{1}+2x_{2}\quad \mathrm {s.t.} \quad &0\leq x_{1}\leq 2,\ x_{1}+x_{2}\leq 1.5,\\&x_{2}\in \mathbb {Z} \end{aligned}}$

Der eindeutige Optimalpunkt ist $x^{\star }=(0.5,1)$, da zunächst die wertvollere ganzzahlige Entscheidungsvariable $x_{2}$ höchstmöglich gewählt wird und anschließend mit der kontinuierlichen Variablen $x_{2}$ „aufgefüllt“ wird. Der Optimalwert lautet $v=0.5+2\cdot 1=2.5$.

Theoretische Aspekte sowie Grundidee der Lösungsmethoden

Lösungsmethoden für MILPs wie das Branch-and-Cut-Verfahren nutzen aus, dass die kontinuierliche Relaxierung des MILPs – also das Optimierungsproblem, welches entsteht, wenn keine Ganzzahligkeit gefordert wird – ein LP ist und somit effizient lösbar ist. Dadurch entsteht zwar in der Regel keine zulässige Lösung des MILPs, aber der Optimalwert lässt sich dadurch im Maximierungsfall nach oben abschätzen. Diese Schranke kann durch das Hinzufügen von Schnittebenen (engl. cutting planes) noch weiter verbessert werden. Gleichzeitig können etwa durch den Einsatz von Heuristiken gute zulässige Punkte berechnet werden, welche im Maximierungsfall in unteren Grenzen an den Optimalwert resultieren. Dadurch lassen sich worst-case Aussagen über die sogenannte MIP Lücke (engl. MIP gap) treffen, wie etwa William Cook und sein Forschungsteam, die eine Rundreise durch 49687 Pubs in UK berechneten und bewiesen, dass keine Tour existieren könne, die auch nur einen Meter kürzer sei.

Optimierungsmethoden, Komplexität und praktische Lösbarkeit

Die kürzeste Tour durch 15112 Städte in Deutschland

Gemischt ganzzahlige Optimierungsprobleme werden durch Branch-and-Bound bzw. Branch-and-Cut-Methoden gelöst. Diese Verfahren besitzen eine theoretisch schlechte Worst-Case-Komplexität, können jedoch durch den Einsatz von Presolve-Techniken, Heuristiken, Schnittebenen und Parallelisierung deutlich beschleunigt werden. Dies ermöglicht in vielen Fällen eine globale Lösung sehr großer Ausprägungen NP-schwerer Probleme, wie etwa das Lösen einer Instanz des Problem des Handlungsreisenden mit 85900 Stationen. Es existieren zahlreiche professionelle Implementierungen von Branch-and-Cut-Methoden. Erwähnt seien die kommerziellen Implementierungen (in alphabetischer Reihenfolge) CPLEX, Gurobi und FICO XPress sowie die Open-Source-Pakete CBC, GLPK und SCIP. Darüber hinaus ist es natürlich auch möglich, (Meta)Heuristiken zur Bestimmung guter zulässiger Punkte von gemischt-ganzzahligen Optimierungsproblemen heranzuziehen.

Geschichte der gemischt-ganzzahligen Optimierung

Ailsa Land, Erfinderin der Branch-and-Bound-Methode

Höhepunkte der Geschichte der gemischt-ganzzahligen Optimierung sind sicher die Erfindung der Branch-and-Bound-Methode von Alisa Land und Alison Doig im Jahre 1960 sowie deren erste professionelle kommerzielle Implementierungen Ende der 1980er Jahre. Für weiterführende Informationen sei auf den nachfolgenden Teilartikel sowie die darin enthaltenen Referenzen verwiesen.

Siehe auch: Mathematische Optimierung#Auszüge aus der Geschichte der mathematischen Optimierung

Weiterführende Literatur

• J. Kallrath: Gemischt-ganzzahlige Optimierung: Modellierung in der Praxis, 2. Auflage. Springer Spektrum, Berlin, Heidelberg, 2013, ISBN 978-3-658-00689-1
• A. Schrijver: Theory of Linear and Integer Programming. Wiley, 1998, ISBN 0-471-98232-6.

• 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.
• L. A. Wolsey: Integer Programming. 2. Auflage. John Wiley & Sons, Hoboken, New Jersey 2020, ISBN 978-1-119-60653-6.