Diskussion:Branch-and-Bound

Die hier beschriebene Algorithmus entspricht zwar einer einer unvollständigen Enumeration, jedoch ist die Beschreibung wie obere und untere Schranken gebildet werden nicht sehr glücklich gewählt. Liegt ein Lineares Optimierungsproblem vor, welches in zwei Teilpropleme separiert wurde, kann unter Umständen ein Teilproblem sofort als vollständig bearbeitet erachtet werden, wenn die untere Schranke (bei einem Maximierungsproblem) größer ist als das Optimum des relaxierten Teilproblems. Darin besteht gerade die Stärke des Branch-and-Bound. Das fehlt hier ein wenig, oder??!!

Sieht ganz brauchbar aus: http://www.bwl.tu-darmstadt.de/bwl3/forsch/projekte/bb/veroeff/bb0197.htm

Tatsächlich sieht die angegebene Seite auf den ersten Blick ganz gut aus. Leider bezieht sich dort der Text im wesentlichen nur auf das Rucksackproblem, und die logischen Tests sind mit Ausnahme der Ganzzahligkeitsüberlegung zu dürftig. Tests wie "Koffer voll" oder "noch genau ein passendes Teil" wirken nur in den Blattspitzen des Verzweigungsbaumes und verkomplizieren den Algorithmus. Derartige Tests helfen aber nicht viel, weil sie nicht allgemein in allen Baumknoten benutzt werden können. Im übrigen sind die Teilprobleme in den Blattspitzen sowieso sehr leicht zu klären, zum Beispiel weil der zulässige Bereich oft leer ist.(nicht signierter Beitrag von 195.72.96.178 (Diskussion) )

Fehler?

Müsste es im letzten Kasten im Abschnitt Lösungsweg nicht

   unter der Nebenbedingung Ax <= b
                              x >=0
                              x1 = t1

anstatt

   unter der Nebenbedingung Ax <= b
                              x >=0
                              x1 = t1

heißen?

Ich verstehe das auch so und habe den Text entsprechend geändert. Aber der Artikel muß insgesamt mal überarbeitet werden. In dem o.g. Absatz ist nicht klar, für welches Problem die Lösung mit x1 = t1 optimal sein soll; es wird oft von oberer und unterer Schranke gesprochen, ohne dass klar ist, ob die Zielfunktion zu minimieren oder zu maximieren ist, und eigentlich ist Branch-and-Bound auch unabhängig von LPs (es wird nur oft auf ganzzahlige lineare Programme angewandt). Mal sehen, vielleicht setze ich mich da am Wochenende mal dran. -- Sdo 00:07, 23. Sep 2005 (CEST)

Tiefen- und Breitensuche

In dem Artikel wird suggeriert Tiefensuche würde schnellere, Breitensuche dafür bessere Ergebnisse liefern. Das stimmt so leider nicht.
- Breitensuche liefert besser Ergebnisse, wenn man von monoton steigenden Pfadkosten entlang des Abstieges im Baum ausgeht
- Tiefensuche kommt nicht schneller zum Ergebnis als Breitensuche, benötigt aber weniger Arbeitsspeicher als diese, da immer maximal ein kompletter Ast im Arbeitsspeicher gehalten werden muss (bereits besuchte Äste können wieder verworfen werden).

  Ich denke, das sind wichtige Punkte.

  Am besten wäre es wohl, jegliche Bewertung der Suchmodi aus dem Artikel zu entfernen, dafür gibt es ja jeweils die spezifischen Artikel zu den Suchmodi, hier lässt sich soetwas dann ausführlicher darstellen.
  Erstens ist Branch and Bound ein exaktes Verfahren das am Ende (wenn man es nicht vorher Abbricht) immer eine bewiesen optimale Lösung liefert (schutzige Details wie numerische Instabilitäten mal außen vor). Hier über bessere Lösungen zu sprechen, ist ziemlich daneben. Zweitens kommen so triviale Suchverfahren in solchen Algorithmen kaum vor, weil man versucht, problemspezifisches Wissen zu nutzen. Dass kann man auch schon bei normalen ganzzahligen Programmen (IP's) tun. Eine sehr einfache und recht gute Strategie ist beispielsweise für IP's zunächst einen Tiefensuche durchzuführen, bis man eine zulässige Lösung gefunden hat. Ab diesem Punkt führt man eine Bestensuche durch, d.h. bei jedem Branch, wählt man den Knoten mit dem besten Zielfunktionswert.

Habe den letzgenannten Punkt in den Artikel aufgenommen, damit die Kombinierbarkeit der Branching-Verfahren klar ist und nicht der Eindruck erweckt wird, es könne nur eines genutzt werden.

Fixierung auf IP's

Erstens Branch and Bound ist kein Verfahren, was aus dem Operations Research kommt, sondern ist letztendlich ein Meta-Verfahren aus der Informatik. Zweitens dient Branch and Bound auch nicht nur zur Lösung von Ganzzahligen Linearen Programmen (IP's) sondern kommt bei vielen speziellen Algorithmen für Kombinatiorische Optimierungsprobleme oder auch Lösungsverfahren im Constraint Programming zum Einsatz. Insgesammt finde ich den Artikel für sehr stark Überarbeitungswürdig. (nicht signierter Beitrag von Tgel2 (Diskussion | Beiträge) )

Du hast mit deinen Einwänden absolut recht. Der Artikel ist grauenhaft und steht auch schon länger auf meiner Todo-Liste, aber im Moment komme ich nicht dazu. Aber wenn du Lust hast, dich daranzusetzen, kann ich ein bisschen mitmachen oder dir zumindest mit Kommentaren zur Seite stehen. :-) -- Sdo 00:41, 28. Aug 2006 (CEST)

Dominanztests

In diskreten Optimierungsproblemen, sowohl linearen als auch nichtlinearen, sollten zusätzlich zur Branch-and-Bound-Methode Dominanztests verwendet werden. Angenommen, ein Maximumproblem sei zu lösen:

$z=f(x)\to \max !\qquad$ bei $\qquad x\in G$

Eine zulässige Lösung $x_{0}$ sei schon bekannt. Branch and bound wird dann die Untersuchung einer Teilmenge $T\subset G$ nicht ablehnen, falls die zugehörige Schranke für $\{f(x):x\in T\}$ größer als $f(x_{0})$ ist, selbst dann, wenn aus jeder Lösung ${\bar {x}}\in T$ eine nicht schlechtere zulässige Lösung ${\tilde {x}}\in G\setminus T$ mit $f({\tilde {x}})\geq f({\bar {x}})$ konstruiert werden kann. Dann aber ist die Untersuchung von $T$ überflüssig. (Falls alle Optimallösungen gesucht werden, ist $f({\tilde {x}})>f({\bar {x}})$ zu fordern.) Dies ist Inhalt der Dominanzüberlegungen. Die Lösung ${\tilde {x}}$ dominiert jeweils ${\bar {x}}$. Auf diese Möglichkeit, den Suchraum einzuschränken, sollte hingewiesen werden.

Eng verwandt mit Dominanztests ist das Ausschließen äquivalenter Situationen. Wenn in einem mehrstufigen Entscheidungsprozeß ein bestimmtes Ergebnis auf verschiedenen Wegen erreicht werden kann, wie etwa in mehrdimensionalen Zuschnitt- und Packungsproblemen, dann braucht eine Situation nicht untersucht werden, wenn sie schon früher erforscht wurde.

Anstelle einer Vorlesung "Zuschnittoptimierung" muß ich noch nach besseren Quellen suchen.

Gandalf Mithrandir 15:50, 5. Apr. 2007 (CEST)

Lösungsweg für ganzzahlige lineare Optimierungsprobleme überarbeitungswürdig

Der Unterabschnitt "Lösungsweg" muß noch präzisiert werden. Wenn eine Zusatzbedingung für $x_{1}$ hinzugefügt wird, dann wird das duale Simplexverfahren auf ein ganzzahliges $x_{1}$ führen, jedoch können andere $x_{i}$, auch wenn sie vorher ganzzahlig waren, nichtganzzahlige Werte annehmen. Dies hatte ich gestern erst im nachhinein bemerkt. Die genauen Formulierungen für die Überarbeitung muß ich mir noch überlegen, bevor ich weiter am Artikel bastele.--Gandalf Mithrandir 13:33, 17. Apr. 2007 (CEST)

Ganzzahligkeitsbedingung an A,b

Diese fehlt meiner ansicht nach noch, damit das Verfahren auch nach der Einschränkung ganzzahlige Werte annimmt. Im Beispiel wurde das ja implizit so vorausgesetzt. Für rationale A,b ist das ja keine Einschränkung. --Ecols 09:52, 3. Apr. 2008 (CEST)

Zweifelhafter Weblink

Diesen zweifelhaften Weblink habe ich mal wieder entfernt. Den Dijkstra-Algorithmus als Branch-and-Bound zu deklarieren, nicht mal die Nebenbedingungen an den Algorithmus zu erwähnen (nichtnegative Kantengewichte) und das Ganze dann auch noch unverständlich zu erklären, ist nicht wirklich hilfreich zum Verständnis. -- Sdo 13:24, 12. Jul. 2008 (CEST)

Notation, Aufbau des Artikels

Hallo, bei der Notation $f(x)\to \min !$ oder auch a*b für ein Skalarprodukt (statt $a^{\mathrm {T} }b$) sträuben sich mir ein wenig die Nackenhaare. Außerdem halte ich den Verweis auf Operations Research im Lemma für irreführend. Auch die Einsortierung in die Kategorie Optimierungsalgorithmus passt meiner Meinung nicht zum Lemma: „Branch-and-Bound [...] ist [...] eine Behandlungsmethode, ein Meta-Verfahren. Für konkrete kombinatorische Optimierungsprobleme ergeben sich dementsprechend angepasste Branch-and-Bound-Algorithmen.“ -- Phil1881 11:48, 14. Sep. 2010 (CEST)

Pruning und Branch and Bound

Ich habe eine Diskussion über den Zusammenhang von Pruning und Branch and Bound gestartet. --Martin Thoma 09:57, 4. Okt. 2012 (CEST)

Ist das nicht ein Backtracking-Algorithmus ?

Im Artikel findet sich bisher kein Verweis auf Backtracking obwohl der Artikel Backtracking prinzipiell die gleiche Kernidee behandelt. (nicht signierter Beitrag von 2A02:810D:4BC0:60C8:51DE:7693:A1D9:775B (Diskussion) 10:50, 12. Jan. 2022 (CET))