Direkt zum Inhalt

Branch-and-Bound-Verfahren

Definition

Verfahren des Operations Research, bei dem ein zu lösendes kombinatorisches Optimierungsproblem (endliche Anzahl unabhängiger Variablen mit diskretem Wertevorrat) keiner effektiven analytischen Behandlung zugänglich ist oder Enumerationsverfahren (Entscheidungsbaumverfahren) wegen des Rechenaufwandes ausscheiden.

GEPRÜFTES WISSEN
Über 200 Experten aus Wissenschaft und Praxis.
Mehr als 25.000 Stichwörter kostenlos Online.
Das Original: Gabler Wirtschaftslexikon

zuletzt besuchte Definitionen...

    Ausführliche Definition

    1. Begriff: Verfahren des Operations Research (OR) zur exakten, d.h. optimalen  Lösung eines (häufig schweren) kombinatorischen Optimierungsproblems (endliche Anzahl unabhängiger Variablen mit diskretem Wertevorrat).

    2. Vorgehensweise: Der Algorithmus verwendet das Prinzip der Aufteilung und Begrenzung des Lösungsraumes. Durch fortwährende Aufteilung des ursprünglichen Problems entsteht eine Baumstruktur, der Branch-and-Bound-Baum. Schritte in jedem Knoten des Baums:
    a) Lösung einer Relaxation, häufig der LP-Relaxation, bei der die Ganzzahligkeitsbedingungen auf den Variablen zunächst weggelassen werden. Folgende Fälle können eintreten: i) die Lösung ist ganzzahlig (dann ist ggf. eine neue beste bekannte zulässige Lösung gefunden; der Knoten muss nicht mehr weiter betrachtet werden); ii) die Lösung ist unzulässig, dann muss der Knoten nicht mehr weiter betrachtet werden; iii) die Lösung hat noch fraktionale, d.h. nicht-ganzzahlige Variablenwerte, obwohl diese ganzzahlig sein sollten.
    b) Branch (Verzweigung): Eine fraktionale Variable wird ausgewählt und zwei neue Teilprobleme gebildet, indem dieser Variablen einmal der nächstgrößere ganzzahlige Wert zugewiesen wird und einmal der nächstkleinere ganzzahlige Wert. Die Auswahl der Variablen erfolgt durch eine Verzweigungsregel (Branchingregel).
    c) Bound (Schranke): Falls die aus der Relaxation gewonnene (sog. duale) Schranke schlechter (d.h. bei einem Minimierungsproblem größer) ist als der Wert einer besten bisher bekannten zulässigen Lösung (sog. primale Schranke), muss der Knoten nicht mehr weiter betrachtet werden. Das Optimum ist erreicht, wenn keine Knoten des Baum mehr offen sind, d.h. noch fraktionale Variablen aufweisen, aber noch nicht verzweigt wurde.

    Die Laufzeit eines Branch-and-Bound-Verfahrens hängt wesentlich von der Qualität der Schranken ab. Für die primale Schranke werden zusätzlich Heuristiken eingesetzt, die duale Schranke hängt von der Qualität der Relaxation ab und wird oft durch zusätzliche Schnittebenen verschärft. Im schlimmsten Fall entartet der Algorithmus zu einer vollständigen Enumeration.

    3. Anwendung: Prinzipiell ist der Algorithmus u.a. auf alle diskreten Probleme anwendbar, v.a. auf gemischt-ganzzahlige Programme oder das Traveling-Salesperson-Problem.

    Mindmap Branch-and-Bound-Verfahren Quelle: https://wirtschaftslexikon.gabler.de/definition/branch-and-bound-verfahren-28551 node28551 Branch-and-Bound-Verfahren node27106 Algorithmus node28551->node27106 node48102 vollständige Enumeration node28551->node48102 node46854 Operations Research (OR) node28551->node46854 node34661 dynamische Optimierung node34929 Entscheidungsbaumverfahren node34929->node28551 node34929->node46854 node35225 Entscheidungsbaum node34929->node35225 node48102->node34661 node48102->node34929 node48102->node46854 node31877 Codierung node31877->node27106 node31993 Implementierung node31993->node27106 node43166 Programm node43166->node27106 node38490 Informatik node38490->node27106 node46576 Spieltheorie node34474 Heuristik node34474->node28551 node48604 Theorie node34474->node48604 node42740 Paradigma node34474->node42740 node42454 Risikomanagement node49361 Supply Chain Management ... node46130 Projektmanagement (PM) node46854->node46576 node46854->node42454 node46854->node49361 node46854->node46130 node34831 Expertenwissen node34831->node34474 node40285 Künstliche Intelligenz (KI) node40285->node34474
    Mindmap Branch-and-Bound-Verfahren Quelle: https://wirtschaftslexikon.gabler.de/definition/branch-and-bound-verfahren-28551 node28551 Branch-and-Bound-Verfahren node46854 Operations Research (OR) node28551->node46854 node27106 Algorithmus node28551->node27106 node48102 vollständige Enumeration node28551->node48102 node34929 Entscheidungsbaumverfahren node28551->node34929 node34474 Heuristik node34474->node28551

    News SpringerProfessional.de

    Autoren der Definition und Ihre Literaturhinweise/ Weblinks

    Literaturhinweise SpringerProfessional.de

    Bücher auf springer.com

    Sachgebiete