Kapitel 3 – Branch-And-Bound

Inhalt

In diesem Kapitel schauen wir uns mit Branch-And-Bound ein weiteres Verfahren zur effizienteren Lösung schwerer algorithmischer Optimierungsprobleme an. Auch für dieses Verfahren betrachten wir unter anderem wieder die Anwendung auf Subset Sum- und Knapsack-Probleme.

Veranstaltungen

  • Übung: Backtracking & Propagation/Exkurs SAT
    In dieser Übung haben wir uns mit Backtracking & Propagation als Ansatz zur Lösung schwerer Entscheidungsprobleme befasst.Dann haben wir in einem kleinen Exkurs das Problem ‘Boolean Satisfiability (SAT)’ betrachtet. Folien
  • Übung 3
    In dieser Übung beschäftigen wir uns mit verschiedenen Beispielen zum Branch-and-Bound Verfahren. Wir schauen uns dabei auch das euklidische Travelling Salesman Problem (TSP) an und machen einen kleinen Exkurs zum Thema Linear/Integer Programming.
  • Vorlesung 6
    In dieser Vorlesung schauen wir uns die Branch-And-Bound Methode in der Anwendung an. Zudem geben wir einige Ausblicke zu weiteren Optimierungsproblemen.
  • Vorlesung 5
    In dieser Vorlesung lernen wir ein alternatives exaktes Verfahren kennen: Branch-And-Bound. Wir schauen uns dabei das Verfahren in seinen Details an und wenden es dann erneut auf das Knapsack-Problem an.