Gemischt-ganzzahlige Optimierung

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

$${\displaystyle \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 ${\displaystyle x^{\star }=(4.5,1.5)}$. Wird jedoch berücksichtigt, dass ${\displaystyle x_{1}}$ ganzzahlig sein muss, so sind alle zulässigen Punkte mit ${\displaystyle x_{1}=4}$ optimal.

Gesucht ist eine gemischt-ganzzahlige Beschreibung der Menge ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle y\in \{0,1\}}$ eingeführt, um folgendes System linearer Ungleichungen zu erhalten:

$${\displaystyle 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 ${\displaystyle M}$ ist. Für ${\displaystyle y=0}$ gilt ${\displaystyle 0\leq x\leq 10}$ und ${\displaystyle 7\leq x\leq 10}$, also insgesamt ${\displaystyle x\in [7,10]}$. Für ${\displaystyle y=1}$ hingegen reduziert sich das System zu ${\displaystyle 0\leq x\leq 3}$ und ${\displaystyle 0\leq x\leq 10}$, also ${\displaystyle x\in [0,3]}$.

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.[10] Die Bedeutung wird dadurch verstärkt, dass sich viele nichtlineare gemischt-ganzzahlige Probleme linear umformulieren oder zumindest linear approximieren lassen.[1][2] 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).

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.

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

${\displaystyle {\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 ${\displaystyle x_{i}}$, ${\displaystyle i\in \{1,\ldots ,n\}}$, bezeichnet und alle sonstigen Parameter bezeichnen feste reelle Zahlen.

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

${\displaystyle {\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 ${\displaystyle L_{i}}$ und ${\displaystyle U_{i}}$ in entsprechenden Vektoren ${\displaystyle L\in \mathbb {R} ^{n}}$ und ${\displaystyle U\in \mathbb {R} ^{n}}$ untergebracht und alle sonstigen Einträge ebenfalls in Vektoren und Matrizen passender Dimension verstaut.

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

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

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.[11]