Branch-and-Bound Verfahren

Das Branch-and-Bound Verfahren nutzt eine Relaxierung, die LP-Relaxierung, aus um ein MIP zu vereinfachen, indem es in Teilprobleme aufgespalten (Branch) wird.

Dabei verwendet es verschiedene Bedingungen (Bound) um nicht alle möglichen Teilprobleme lösen zu müssen:

Ein Verfahren zum lösen von Gemischt-ganzzahligen linearen Optimierungsproblemen.

Für das Problem lässt sich der ZFW beschränken:

  • z^\hat{z} → Wert einer Optimallösung x^\hat{x} von LP
  • z∗z^* → Wert einer Optimallösung x∗x^* von MIP

Es gilt:

z^≤z∗\hat{z}\leq z^*

denn mit der Relaxierung kann ein besserer ZFW durch eine für MIP unzulässige Lösung gefunden werden. Wenn aber z^\hat{z} für MIP zulässig ist, dann ist es bereits die Optimallösung.

Das Problem lässt sich in Teilprobleme zerlegen:

  • Sei xx gemischt-ganzzahlig
  • Sei s:=x^j∉Zs:=\hat{x}_j\notin\mathbb{Z} mit j∈{ 1,...,p }j\in\set{1,...,p}

Dann ist

  • xx zulässig für MIP mit xj≤⌊s⌋x_j\leq\lfloor s \rfloor oder
  • xx zulässig für MIP mit xj≥⌈s⌉x_j\geq\lceil s \rceil

Seien

Zwei Annahmen müssen getroffen werden:

  1. LP-Relaxierung besitzt keine zulässige Lösung oder eine Optimallösung, ist also nicht unbeschränkt.
  2. Alle Koeffizienten in AA und bb sind rational (siehe Übung 7)

Vorgehen

Löse die LP-Relaxierung, dabei kann es zu folgenden Fällen kommen:

1. LP Relaxierung liefert eine ganzzahlige Lösung

Wenn die LP-Relaxierung eine ganzzahlige Lösung ergibt, so ist MIP gelöst.

2. LP Relaxierung liefert eine fraktionale Lösung

Wenn die LP-Relaxierung keine ganzzahlige Lösung ergibt, so ist die Lösung ein Wert ss, der nicht ganzzahlig ist. Partitioniere SS mit

S1:=S∩{x:xj≤⌊s⌋},S2:=S∩{x:xj≥⌈s⌉}S_{1}:=S \cap\left\{x: x_{j} \leq\lfloor s\rfloor\right\}, \quad S_{2}:=S \cap\left\{x: x_{j} \geq\lceil s\rceil\right\}

Daraus entstehen zwei MIPs.

Stelle für die beiden MIPs die entsprechenden LP-Relaxierungen auf mit

P1:=P∩{x:xj≤⌊s⌋},P2:=P∩{x:xj≥⌈s⌉}P_{1}:=P \cap\left\{x: x_{j} \leq\lfloor s\rfloor\right\}, \quad P_{2}:=P \cap\left\{x: x_{j} \geq\lceil s\rceil\right\}

Beim lösen der LP-Relaxierungen können folgende Fälle auftreten:

  1. Prune by Infeasibility
  2. Prune by Integrality
  3. Prune by Bound
  4. Wenn das Problem einen kleineren ZFW als die beste obere Schranke (Prune by Integrality) hat, dann kann SiS_i noch eine optimale Lösung enthalten. Es wird also erneut partitioniert mit si:=x^jis_{i}:=\hat{x}_{j}^{i} und den Mengen Si1S_{i1} und Si2S_{i2}. Der Vorgang wird wiederholt.

Terminiertheit

Der Algorithmus stoppt, wenn alle Teilprobleme abgearbeitet sind. Das passiert in endlich vielen Schritten, wenn die ganzzahligen Variablen beschränkt sind. Die Anzahl an Teilproblemen kann aber exponentiell in der Anzahl der ganzzahligen Variablen wachsen.

Implementierung

Für eine effiziente Implementierung muss noch eine passende Node Selection Rule in Schritt 3 und Branching Rule in Schritt 13 des Algorithmus festgelegt werden.

Algorithmus

Bildschirmfoto 2022-06-23 um 20.20.33.png

Beispiel

min⁡{−5.5x1−2.1x2:−x1+x2≤2,8x1+2x2≤17,x1,x2≥0,x1,x2∈Z}\min \left\{-5.5 x_{1}-2.1 x_{2}:-x_{1}+x_{2} \leq 2,8 x_{1}+2 x_{2} \leq 17, x_{1}, x_{2} \geq 0, x_{1}, x_{2} \in \mathbb{Z}\right\}

Oft wird ein Graph als Darstellung des Verfahrens verwendet:

Bildschirmfoto 2022-06-23 um 20.21.02.png