19
Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP- Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Embed Size (px)

Citation preview

Page 1: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 1

Branch and Bound

Das Verfahren zur Lösung von IP-Problemen

Idee * Entscheidungsbaum * Lösungen

Page 2: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 2

Branching

Branching = Verzweigen Eine sinnvolle Verzweigung muss ein im

Prinzip in einfacher zu lösende Probleme erfolgen.

Beim Verzweigen durch Problemteilung darf keine relevante Lösung verloren gehen.

Page 3: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 3

Bounding

Bounding = Beschränken Für Max-Probleme sucht man obere

Schranken Für Min-Probleme untere Schranken Das relaxierte Problem liefert immer eine

obere bzw. untere Schränke

Page 4: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 4

Entscheidungsbaum

Page 5: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 5

Abbruchkriterien (1)

FC1: L(LPj) = Ø → L(IPj) = Ø

FC2: Lösung des LPj ist schlechter als die beste bisher bekannte Lösung des IP:zj ≤ zlfd

FC3: Falls die Lösung von LPj eine Lösung des IPj ist, wird geprüft, ob sie besser ist als die beste bekannte Losung: zj > zlfd → zlfd*= zj

Page 6: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 6

Abbruchkriterien (2)

Page 7: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 7

Branch and Bound – Beispiel LP0

1 2

1 2

1 2

Max

mit 21 11

u.d.N. 6x 4 15

, 0

z

z x x

x

x x

Max x1 x2 RS Max x3 x2 RS

z0 21 11 0 z0 72 3 521

2

x3 6 4 15 x1 16 2

3 52

1 1entweder ist 2 oder 3x x

Page 8: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 8

B&B – Graph LP0

Page 9: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 9

B&B – LP11 und LP12

Max x1 x2 RS Max x1' x2 RS Max x1' x3 RS

z11 21 11 0 z11 21 11 42 z11 9

2 114 501

4

x3 6 4 15 x3 6 4 3 x2 32 1

4 34

x1' 1 0 2 x1 1 0 2 x1 1 2

Max x1 x2 RS Max x4 x2 RS

z21 21 11 0 z21 21 11 63

x3 6 4 15 x3 6 4 3 keine zul. Lösung!

x4 1 0 3 x1 1 0 3

Page 10: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 10

B&B – Graph LP11 und LP12

Page 11: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 11

B&B – Baumtiefe 1

0 0

51 22

: 52,5

; 0

LP z

x x

1 2x

0 0

51 22

: 52,5

; 0

LP z

x x

12 :

FC1

LP 11 11

1 2

: 50,25

2; 0,75

LP z

x x

1 3x 1 2x

0 0

51 22

: 52,5

; 0

LP z

x x

Page 12: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 12

B&B – Graph LP21 und LP22

Page 13: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 13

B&B – Baumtiefe 2

2 0x

22 22

1 2

: 49,5

11/ 6; 1

LP z

x x

21 21

1 2

: 42

2; 0

LP z

x x

0 0

51 22

: 52,5

; 0

LP z

x x

1 3x 1 2x

11 11

1 2

: 50,25

2; 0,75

LP z

x x

12 :

FC1

LP

2 1x 2 0x 2 1x

21 21

1 2

: 42

2; 0

LP z

x x

FC1

Page 14: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 14

B&B – Grph LP31 und LP 32

Page 15: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 15

B&B – Baumtiefe 3

22 22

1 2

: 49,5

11/ 6; 1

LP z

x x

0 0

51 22

: 52,5

; 0

LP z

x x

1 3x 1 2x

11 11

1 2

: 50,25

2; 0,75

LP z

x x

12 :

FC1

LP

2 0x 2 1x

21 21

1 2

: 42

2; 0

LP z

x x

331 31 4

11 2 4

: 43

1; 2

LP z

x x

32 :

FC1

LP

1 1x 1 2x

FC1

FC3

Page 16: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 16

B&B – Graph LP41 und LP42

Page 17: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 17

B&B – Vollständiger Entscheidungsbaum

41 31

1 2

: 43

1; 2

FC3

LP z

x x

142 42 2

11 22

: 43

; 3

FC2

LP z

x x

22 22

1 2

: 49,5

11/ 6; 1

LP z

x x

0 0

51 22

: 52,5

; 0

LP z

x x

1 3x 1 2x

11 11

1 2

: 50,25

2; 0,75

LP z

x x

12 :

FC1

LP

2 0x 2 1x

21 21

1 2

: 42

2; 0

FC3

LP z

x x

2 1x 1 2x

331 31 4

11 2 4

: 43

1; 2

LP z

x x

32 :

FC1

LP

2 2x 2 3x

Page 18: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 18

B&B – Problemlösung

Da alle Knoten abgearbeitet sind, ist die gesuchte Lösung erreicht und …

…es wurde nachgewiesen, dass die Lösung wirklich optimal ist.

Branching: Grundsätzlich auch in mehr als einen Knoten möglich. Alle so erzeugten Knoten kommen in die sog. Kandidatenliste.

Bounding: An dieser Stelle können alle Hilfsmittel eingesetzt werden, um eine möglichst Schranke zu berechnen.

Page 19: Branch and Bound 1 Branch and Bound Das Verfahren zur Lösung von IP-Problemen Idee * Entscheidungsbaum * Lösungen

Branch and Bound 19

B&B – Vor- und Nachteile

Anbindung an den LP-Modul Gestaltungsfreiheit des Baumbaus Heuristische Unterstützung Verwendbarkeit der Lösung bei Abbruch Hoher Speicheraufwand Hoher Rechenaufwand Veränderliche Problemgröße