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.

    zuletzt besuchte Definitionen...

      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 node34929 Entscheidungsbaumverfahren node28551->node34929 node48102 vollständige Enumeration node28551->node48102 node42988 Programmablaufplan node42988->node27106 node54006 Sintflutalgorithmus node34474 Heuristik node54006->node34474 node34831 Expertenwissen node34831->node34474 node47812 Wissenschaftstheorie node34474->node28551 node34474->node47812 node50687 Unterprogramm node50687->node27106 node51203 Zufallsgenerator node51203->node27106 node26936 binäre Suche node26936->node27106 node40139 Netzplantechnik node46854->node40139 node29078 begrenzte Enumeration node35225 Entscheidungsbaum node34929->node46854 node34929->node29078 node34929->node35225 node34929->node48102 node47840 Warteschlangentheorie node47840->node46854 node48102->node46854 node48102->node29078 node35403 Ersatzprobleme node35403->node46854 node54005 Simulated Annealing node54005->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 node34929 Entscheidungsbaumverfahren node28551->node34929 node27106 Algorithmus node28551->node27106 node48102 vollständige Enumeration node28551->node48102 node34474 Heuristik node34474->node28551

      News SpringerProfessional.de

      • Exportentwicklung Werkzeugmaschinen

        Ein aktueller Quest Report verbindet Exportmärkte und Durchschnittswerte von Werkzeugmaschinen in Euro und die Wirkung auf die Exporte nach China seit 2008. Steigende Durchschnittswerte von Werkzeugmaschinen gehen demnach mit rückläufigen Exporten nach China einher.

      • Banken genießen großes Vertrauen ihrer Kunden

        72 Prozent der Bankkunden in Deutschland gehen davon aus, dass Kreditinstitute mit ihren persönlichen Daten sorgsam umgehen. Keine andere Branche genießt einer aktuellen Umfrage zufolge höheres Vertrauen.

      • Neue Aufgaben für die Zentrale der Zukunft

        Unternehmen müssen agil und innovativ sein. Das althergebrachte Headquarter, von dem aus alles zentral gesteuert werden soll, scheint dazu nicht passen zu wollen. Muss die Unternehmenszentrale neu erfunden werden? 

      • So geht erfolgreiches Lead Nurturing im B2B-Segment

        Wenn nicht nur Leads, sondern in Folge auch Käufer generiert werden, ist von Lead Nurturing die Rede. Im B2B-Bereich müssen E-Mail-Marketer dafür besonders strategische sowie kontinuierliche Beziehungsarbeit leisten.

      • Globales E-Invoicing ist Herausforderung für Unternehmen

        Unternehmen sind aufgrund staatlicher Vorgaben zunehmend dazu verpflichtet, ihre Rechnungen elektronisch zu erstellen. Doch in jedem Land gelten andere rechtliche Regelungen. Entsprechend komplex gestalten sich die Prozesse. Erster Teil des Gastbeitrags.

      • Auf dem Rechtsweg ins Verderben

        Wer seinen Markt als Eigentum betrachtet und Neueinsteiger juristisch bekämpfen will, kann nur verlieren, meint Springer-Autor und Zukunftsmanager Heino Hilbig. Denn die Klage eines Taxifahrers gegen Moia wird neue Verkehrskonzepte nicht verhindern. 

      • Mit Location Based Marketing auf Neukundenfang

        Deutsche Marketing-Manager sehen in standortbasierter Werbung die Brücke, um Konsumenten online wie offline anzusprechen. Vor allem für die Neukundengewinnung setzen sie auf das Marketinginstrument.

      • Wie der Arbeitsplatz von morgen aussehen wird

        Während der Industrialisierung wanderte die Arbeit aus dem Haushalt in die Fabrik. Heute klopft sie wieder an die Haustür. Die Möglichkeit zu mehr zeitlicher und örtlicher Flexibilität, beispielsweise zur Arbeit im Homeoffice, macht vor keiner Branche mehr halt.

      • Java und JavaScript sind die beliebtesten Programmiersprachen

        Die meisten Softwareingenieure setzen auf Java und JavaScript, wenn es um die Entwicklung von Unternehmensanwendungen geht. Die angeblichen "In"-Programmiersprachen Python & Co. liegen in der Beliebtheitsskala teils weit abgeschlagen hinter den Klassikern.

      • Diese digitalen Marken sind top

        Digitale Dienste dominieren immer stärker die Markenwelt. In den Top 25 der relevantesten Marken Deutschlands machen sich analoge Marken eher rar.

      Autoren der Definition und Ihre Literaturhinweise/ Weblinks

      Prof. Dr. Marco Lübbecke
      RWTH Aachen, Lehrstuhl für Operations Research
      Lehrstuhlinhaber

      Literaturhinweise SpringerProfessional.de

      Springer Professional - Die Flatrate für Fachzeitschriften und Bücher
      Dieses Kapitel stellt nach einer kurzen Einführung in die Konzeption von Branch-and-Bound-Verfahren ein neues Lösungsverfahren für Fixkosten-Netzwerkflußprobleme vor. Das Laufzeitverhalten dieses Verfahrens, das die Problemlöser aus Kapitel 3 zur …
      Ausgangspunkt sei weiterhin das in der Einleitung zu Teil IV zugrundegelegte Problem (P), mit endlichen Unter- und Obergrenzen für den Vektor x1. Vorausgesetzt wird, daß die Aufgabe (Pst) lösbar sei. — Um das Simplexverfahren zur Lösung von (P) …
      Das Branch-and-Bound-Verfahren gehört mit der Begrenzten Enumeration und der Dynamischen Planungsrechnung zu den Entscheidungsbaumverfahren und steht mit ihnen der Vollständigen Enumeration gegenüber. Während man bei der Begrenzten Enumeration …

      Sachgebiete