Diskrete Optimierung: Fallstudien aus der Praxis Branch and Bound – Grundlagen Barbara Langfeld, Michael Ritter, Barbara Wilhelm Technische Universität München 20A Ganzzahlige Programmierung c x2 max c T x P Ax ≤ b x ≥0 x ∈ Zn x1 B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Ganzzahlige Programmierung c x2 max c T x P Ax ≤ b x ≥0 x ∈ Zn PI x1 B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branching c ! LP-Relaxation: x (0) = x2 1.5 2.5 x (0) P x1 B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branching c ! LP-Relaxation: (0) x1 ∈ /Z x (0) = x2 1.5 2.5 Teilprobleme: x (0) P x1 B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branching ! LP-Relaxation: (0) x1 ∈ /Z x (0) x2 1.5 2.5 = x (0) Teilprobleme: j (0) x1 ≤ x1 k P =1 P (1) x1 B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branching ! LP-Relaxation: (0) x1 ∈ /Z x (0) x2 1.5 2.5 = Teilprobleme: j (0) k =1 (0) m =2 x1 ≤ x1 l oder x1 ≥ x1 x (0) P P (2) x1 B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branching ! LP-Relaxation: (0) x1 ∈ /Z x (0) x2 1.5 2.5 = Teilprobleme: j (0) k =1 (0) m =2 x1 ≤ x1 l oder x1 ≥ x1 P (1) P (2) für jedes Teilproblem: Prozedur wiederholen x1 B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branching ! LP-Relaxation: (0) x1 ∈ /Z x (0) x2 1.5 2.5 = Teilprobleme: j (0) k =1 (0) m =2 x1 ≤ x1 l oder x1 ≥ x1 P (1) P (2) für jedes Teilproblem: Prozedur wiederholen x1 Branching B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Bounding c x2 x (0) P x1 beste Lösung: ?? Zielfunktionswert: B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis ?? Bounding c x2 P (1) P (2) x1 beste Lösung: ?? Zielfunktionswert: B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis ?? Bounding c x2 x (2) P (2) x1 beste Lösung: ?? Zielfunktionswert: B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis ?? Bounding c x2 x (2) P (2) x1 beste Lösung: ?? Zielfunktionswert: B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis ?? Bounding c x2 x (3) P (3) x1 beste Lösung: ?? Zielfunktionswert: B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis ?? Bounding c x2 x (3) P (3) x1 beste Lösung: ?? Zielfunktionswert: B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis ?? Bounding c x2 x (5) P (5) x1 beste Lösung: ?? Zielfunktionswert: B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis ?? Bounding c x2 x (5) P (5) x1 beste Lösung: (2, 1)T Zielfunktionswert: B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis 3 Bounding c x2 x (1) P (1) x1 beste Lösung: (2, 1)T Zielfunktionswert: B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis 3 Bounding c x2 x (1) T (1) c x = 2.5 P (1) x1 beste Lösung: (2, 1)T Zielfunktionswert: B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis 3 Bounding c x2 x (1) T (1) c x = 2.5 P (1) x1 Bounding B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branch & Bound: Überblick Initialisieren Ende Nein Ja Knoten übrig? Knotenauswahl Schranken bestimmen Knoten abschneiden ? Ja Nein Branching B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branch & Bound: Bestandteile Knotenauswahl: Welches Teilproblem zuerst? Schranken: Woher gute globale und lokale Schranken? Abschneiden: Baum möglichst klein halten! Branching: Wieviele und welche Teilprobleme? B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branch & Bound für ILP Knotenauswahl Schranken Abschneiden allgemein zulässige Lösung finden Schranken verbessern Baum klein halten gute Lösung finden für ILP Teilproblem Teil-Polyeder Güteschätzung: Dualitätslücke B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branching Branch & Bound für ILP Knotenauswahl Schranken Abschneiden Branching allgemein globale untere Schranke: Mindestwert der Lösung lokale obere Schranken: Höchstwert der Lösung in Teilproblem gute Schranken kleiner Baum Rechenaufwand für ILP global: zulässige ganzzahlige Lösung, Heuristik lokal: LP-Relaxation B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branch & Bound für ILP Knotenauswahl Schranken Abschneiden Branching allgemein lokale Schranke < globale Schranke Abschneiden Baum klein halten evtl. vorzeitiger Abbruch Güte der Lösung? für ILP Vergleich der Schranken B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branch & Bound für ILP Knotenauswahl Schranken Abschneiden allgemein wenige Zweige, kleiner Baum schnell Lösung finden gute Schranken für ILP fraktionelle Komponente wählen auf- und abrunden, evtl. mehrere Zweige andere Ideen kommende Stunden B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Branching Zusammenfassung: Branch & Bound allgemein exakter Algorithmus Prototyp, Details müssen festgelegt werden entscheidend: gute Schranken, Branching, Knotenauswahl B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis Zusammenfassung: Branch & Bound allgemein exakter Algorithmus Prototyp, Details müssen festgelegt werden entscheidend: gute Schranken, Branching, Knotenauswahl für ILP wichtigster ILP-Algorithmus in der Praxis Performancegarantie: Dualitätslücke problemangepasste Strategien hilfreich Kombinationen mit Heuristiken, Approximationsalgorithmen, Schnittebenen-Verfahren B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis
© Copyright 2024 ExpyDoc
