Branching

Branching hilft beim Finden einer Lösung eines ganzzahligen Optimierungsproblems. Dabei wird das Problem in mehrere Instanzen aufgeteilt, die dann unabhängig voneinander gelöst werden. Dabei erhält man Bounds (Schranken), die durch weitere Instanzen verbessert werden können.

Anwendung

Eine Variable soll ganzzahlig sein, hat aber eine reell-wertige Lösung . Um das zu lösen, teilt man das Problem in zwei Inszanzen auf, eine mit der Nebenbedingung und die andere mit Nebenbedingung .

Beim Lösen der Instanz kann man auf folgende Fälle stoßen:

1. Die Lösung ist wieder reell-wertig - Dann teilt man das Problem wieder in 2 weitere Instanzen und wiederholt die Schritte.
2. Die Lösung ist ganzzahlig - Dann bildet die Lösung eine erste untere Schranke. Beim Lösen weiterer Instanzen wird geschaut, ob das Ergebnis größer ist als die aktuelle Schranke. Falls ja, wird die Schranke aktualisiert.

Anmerkung

• Ist die Schranke gleich der abgerundeten Lösung der LP-Relaxion, kann die Lösung nicht mehr besser werden und das Verfahren kann beendet werden.

Best Bound Search

Eine Heuristik, um eine Instanz auszuwählen, ist Best Bound Search. Dabei wird die Instanz mit dem besten Bound gelöst. Falls man dort eine ganzzahlige Lösung findet, kann die Suche abgebrochen werden.