Branching

Das zu lösende, komplexe Optimierungsmodell bzw. Problem wird als Ausgangsproblem bezeichnet. Dieses wird im Rahmen des Branching (Verzweigung) in eine Anzahl von Teilproblemen P1, ..., Pk zerlegt, so dass jedes Teilproblem lediglich eine Teilmenge der zulässigen Lösungen von repräsentiert und somit i.d.R. leichter zu lösen ist. Dabei ist darauf zu achten, dass jede zulässige Lösung von in der Lösungsmenge mindestens eines der Teilprobleme enthalten ist. Durch fortgesetzte Verzweigung von Teilproblemen ergibt sich ein Baum (B&B-Baum) mit Problem als Wurzel. Teilprobleme (Knoten des Baums), die im Rahmen des Bounding ausgelotet werden können, werden nicht mehr verzweigt. Die Struktur und die Größe des B&B-Baums (und damit der Rechenaufwand zu seiner Auswertung) hängen wesentlich von der Ausgestaltung der Verzweigungsoperation ab, die festlegt, wie die Zerlegung in Teilprobleme erfolgt. Bei der Lösung binärer Optimierungsmodelle, wie dem des Knapsack-Problems, besteht eine intuitive Verzweigungsoperation darin, für jeden Knoten zwei Teilprobleme zu bilden. In einem wird der Wert einer Binärvariablen auf 0 und im anderen auf 1 gesetzt. Dadurch zerfällt die Lösungsmenge von in zwei disjunkte Teilmengen.

<< vorhergehender Begriff

nächster Begriff >>

Branchenvergleich

Branching-Regeln