Branching-Regeln

Beim Branching ist festzulegen, in welcher Reihenfolge die Knoten des B&B-Baums erzeugt und weiter verzweigt werden sollen.

• LIFO-Regel: Es wird zunächst jeweils nur das erste Teilproblem eines Knotens gebildet und zu diesem übergegangen. Dies wird so lange wiederholt, bis man einen Knoten ausloten kann. Danach geht man zurück und folgt dem nächstmöglichen Teilproblem wieder „in die Tiefe“ usw.
• Maximum Upper Bound-Regel: Man bildet alle Teilprobleme des aktuellen Knotens, berechnet dafür obere Schranken und speichert sie – sortiert in monoton fallender Ordnung der Schranken – in einer so genannten Kandidatenliste. Aus dieser Liste wird jeweils der erste Knoten (mit größter oberer Schranke) gewählt und weiter verzweigt. Bei zu minimierender Zielfunktion ist analog eine Minimal Lower Bound-Regel anzuwenden. Beim Branching ist u.a. außerdem zu entscheiden, welche Variable xh zum Verzweigen gewählt wird. Solche Auswahlregeln basieren zumeist auf der Berechnung von Prioritätswerten. Z.B. kann man stets eine ganzzahlige Variable auswählen, die in der Lösung der LP-Relaxation den größten (oder kleinsten) nichtganzzahligen Anteil oder den größten Zielfunktionskoeffizienten aufweist.

<< vorhergehender Begriff

nächster Begriff >>

Branching

Brand design