Diskrete Optimierung: Fallstudien aus der Praxis · 2009-05-12 · Diskrete Optimierung:...

Diskrete Optimierung: Fallstudien aus der PraxisBranch and Bound – Grundlagen

Barbara Langfeld, Michael Ritter, Barbara Wilhelm

Technische Universität München

20A

Ganzzahlige Programmierung

max cT xAx ≤ bx ≥ 0x ∈ Zn

x1

x2

P

c

B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Ganzzahlige Programmierung

max cT xAx ≤ bx ≥ 0x ∈ Zn

x1

x2

P

c

PI

B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Branching

LP-Relaxation: x (0) =

(1.52.5

)

x (0)1 /∈ Z Teilprobleme:

x1 ≤⌊x (0)

1

⌋= 1

oder x1 ≥⌈x (0)

1

⌉= 2

für jedes Teilproblem:Prozedur wiederholen

x1

x2

P

c

x (0)

Branching

B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Branching

LP-Relaxation: x (0) =

(1.52.5

)x (0)

1 /∈ Z Teilprobleme:

x1 ≤⌊x (0)

1

⌋= 1

oder x1 ≥⌈x (0)

1

⌉= 2

für jedes Teilproblem:Prozedur wiederholen

x1

x2

P

c

x (0)

Branching

B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Branching

LP-Relaxation: x (0) =

(1.52.5

)x (0)

1 /∈ Z Teilprobleme:

x1 ≤⌊x (0)

1

⌋= 1

oder x1 ≥⌈x (0)

1

⌉= 2

für jedes Teilproblem:Prozedur wiederholen

x1

x2

P

P(1)

x (0)

Branching

B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Branching

LP-Relaxation: x (0) =

(1.52.5

)x (0)

1 /∈ Z Teilprobleme:

x1 ≤⌊x (0)

1

⌋= 1

oder x1 ≥⌈x (0)

1

⌉= 2

für jedes Teilproblem:Prozedur wiederholen

x1

x2

P

P(2)

x (0)

Branching

B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Branching

LP-Relaxation: x (0) =

(1.52.5

)x (0)

1 /∈ Z Teilprobleme:

x1 ≤⌊x (0)

1

⌋= 1

oder x1 ≥⌈x (0)

1

⌉= 2

für jedes Teilproblem:Prozedur wiederholen

x1

x2

P(1) P(2)

Branching

B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Branching

LP-Relaxation: x (0) =

(1.52.5

)x (0)

1 /∈ Z Teilprobleme:

x1 ≤⌊x (0)

1

⌋= 1

oder x1 ≥⌈x (0)

1

⌉= 2

für jedes Teilproblem:Prozedur wiederholen

x1

x2

P(1) P(2)

BranchingB. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Bounding

x1

x2

c

Px (0)

beste Lösung: ?? Zielfunktionswert: ??B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Bounding

x1

x2

c

P(1) P(2)

beste Lösung: ?? Zielfunktionswert: ??B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Bounding

x1

x2

c

P(2)

x (2)

beste Lösung: ?? Zielfunktionswert: ??B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Bounding

x1

x2

c

P(2)

x (2)

beste Lösung: ?? Zielfunktionswert: ??B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Bounding

x1

x2

c

P(3)

x (3)

beste Lösung: ?? Zielfunktionswert: ??B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Bounding

x1

x2

c

P(3)

x (3)

beste Lösung: ?? Zielfunktionswert: ??B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Bounding

x1

x2

c

P(5)

x (5)

beste Lösung: ?? Zielfunktionswert: ??B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Bounding

x1

x2

c

P(5)

x (5)

beste Lösung: (2, 1)T Zielfunktionswert: 3B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Bounding

x1

x2

c

P(1)

x (1)

beste Lösung: (2, 1)T Zielfunktionswert: 3B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Bounding

x1

x2

c

P(1)

x (1)

cT x (1) = 2.5

beste Lösung: (2, 1)T Zielfunktionswert: 3B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Bounding

x1

x2

c

P(1)

x (1)

cT x (1) = 2.5

BoundingB. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Branch & Bound: Überblick

Initialisieren Ende

Knotenauswahl Knoten übrig?

Schranken bestimmen

Knoten abschneiden ?

Branching

Ja

Nein

JaNein

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 Branching

allgemein

zulässige Lösung findenSchranken verbessernBaum klein haltengute Lösung finden

für ILP

Teilproblem Teil-PolyederGüteschätzung: Dualitätslücke

B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Branch & Bound für ILP

Knotenauswahl Schranken Abschneiden Branching

allgemein

globale untere Schranke: Mindestwert der Lösunglokale obere Schranken: Höchstwert der Lösungin Teilproblemgute Schranken kleiner BaumRechenaufwand

für ILP

global: zulässige ganzzahlige Lösung, Heuristiklokal: 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 AbschneidenBaum klein haltenevtl. 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 Branching

allgemein

wenige Zweige, kleiner Baumschnell Lösung findengute Schranken

für ILP

fraktionelle Komponente wählenauf- und abrunden, evtl. mehrere Zweigeandere Ideen kommende Stunden

B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Zusammenfassung: Branch & Bound

allgemein

exakter AlgorithmusPrototyp, Details müssen festgelegt werdenentscheidend: gute Schranken, Branching, Knotenauswahl

für ILP

wichtigster ILP-Algorithmus in der PraxisPerformancegarantie: Dualitätslückeproblemangepasste Strategien hilfreichKombinationen mit Heuristiken, Approximationsalgorithmen,Schnittebenen-Verfahren

B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis

Zusammenfassung: Branch & Bound

allgemein

exakter AlgorithmusPrototyp, Details müssen festgelegt werdenentscheidend: gute Schranken, Branching, Knotenauswahl

für ILP

wichtigster ILP-Algorithmus in der PraxisPerformancegarantie: Dualitätslückeproblemangepasste Strategien hilfreichKombinationen mit Heuristiken, Approximationsalgorithmen,Schnittebenen-Verfahren

B. Langfeld, M. Ritter, B. Wilhelm | Diskrete Optimierung: Fallstudien aus der Praxis