Branch-and-Bound am Minimierungsproblem (optimale Lösung)

Es soll im folgenden das Branch-and-Bound Verfahren anhand eines ganzzahligen Minimierungsproblems dargestellt werden. Es wird hier zur Festlegung der Schranken nicht das Ausgangsproblem betrachtet, sondern das angepasste Problem . Dazu wird für das gegebene ganzzahlige Minimierungsproblem die Ganzzahligkeitsbedingung vernachlässigt und zunächst mittels Simplex-Algorithmus oder grafisch die optimale Lösung für jedes Teilproblem ermittelt. Diese ermittelte optimale Lösung wird dann in die Zielfunktion eingesetzt und der optimale Zielfunktionswert bestimmt. 

Bestimmung der oberen Schranke für den 0. Ast

Das angepasste Minimierungsproblem muss zunächst in die Standardform (Maximierungsproblem, -Nebenbedingungen, Nichtnegativitätsbedingung) umgeformt werden. Danach wird es in die Normalform überführt. Sind auf der rechten Seite keine negativen Werte gegeben, so kann sofort der primale Simplexalgorithmus angewandt werden um eine optimale Lösung zu erhalten. Sind negative Werte auf der rechten Seite gegeben, so wird zunächst der duale Simplexalgorithmus angewandt um eine zulässige Lösung zu erhalten. Danach kann der primale Simplexalgorithmus angewandt werden. Die ermittelte optimale Lösung wird dann in die Zielfunktion eingesetzt. 

Der ermittelte optimale Zielfunktionswert wird dann als untere Schranke  gewählt. 

Zusätzlich zu der lokalen unteren Schranke muss noch eine obere Schranke für den 0. Ast betrachtet werden, welche nicht überschritten werden darf. Diese ist bei Minimierungsproblemen gegeben durch .

Das Problem wird dann in zwei Teilprobleme und verzweigt. Begonnen wird mit derjenigen Variablen, die den größten optimalen Wert aufweist. 

Die resultierenden Teilprobleme müssen dann separat betrachtet werden und wieder mittels Simplexalgorithmus oder grafisch die optimale Lösung unter Vernachlässigung der Ganzzahigkeitsbedingung bestimmt werden, indem die verzweigten Nebenbedingungen eingesetzt werden. Ein Teilproblem braucht nicht weiter betrachtet werden, wenn gilt:

Das Branch-and-Bound-Verfahren wird im folgenden Abschnitt anhand eines Beispiels dargestellt.