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.

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.Branching-Regeln 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 Fachbegriff: Branchenvergleich | Nächster Fachbegriff: Branching-Regeln

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : Marketing-Lehre | Krankenversicherungsschutz | Meldewesen, außenwirtschaftliches

Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

Marketing

Definition

Konditionenpolitik

Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

Investitionsrechnungen

Marktversagen

Umsatzsteuer