Zusammenfassung Branch and Bound PDF

Preview

Summary

Branch and Bound Thematik...

Description

Zusammenfassung Branch and Bound Ganzzahlige und gemischt-ganzzahlige Programme • • •

Ganzzahlige Programme (integer): LP, deren Variablen nur ganzzahlige Werte annehmen dürfen Gemischt-ganzzahlige Programme (mixed integer): LP, die kontinuierliche und ganzzahlige Variablen enthalten Binäre Programme (binary): LP, deren Variablen nur die Werte 0 und 1 annehmen dürfen LP Relaxation: Vernachlässigung (relaxieren) der Ganzzahligkeitsbedingungen

→ der optimale Zielfunktionswert des relaxierten LP ist bei einem Maximierungsproblem die obere Schranke für den Zielfunktionswert der optimalen Lösung des Ganzzahligen Programms (bei Minimierungsproblem: untere Schranke) Branch-and-Bound Verfahren (hier mit B&B abgekürzt) Verfahren zur Lösung gemischt-ganzzahliger Programme → zentrale Idee: zunächst optimale Lösung des relaxierten Problems suchen! Folgende vier Fälle können auf die Teilprobleme zutreffen: 1. ganzzahlige Entscheidungsvariablen (integer) (dadurch zulässige Lösung des Ganzzahligen Problems) 2. z liegt außerhalb der Schranken (z unter der unteren Schranke für Maximierungsproblem, z über der oberen Schranke für Minimierungsproblem) 3. Keine zulässige Lösung (infeasible) (Nebenbedingungen des Teilproblems schließen sich gegenseitig aus) 4. Entscheidungsvariablen nicht ganzzahlig (nicht integer) (und z innerhalb der Schranken) → verzweigen (branching) Auswahlregeln: • • • •

LIFO (last in - first out): zuletzt gebildete Teilprobleme werden zuerst behandelt FIFO (first in - first out): zuerst gebildete Teilprobleme werden zuerst behandelt MUB (maximum upper bound): Teilproblem mit dem maximalen Zielfunktionswert wird zuerst ausgewählt (→ absteigend sortiert) MLB (minimum lower bound): Teilproblem mit dem minimalen Zielfunktionswert wird zuerst ausgewählt (→ aufsteigend sortiert)

Begrenztes Branch-and-Bound (Truncated Branch & Bound) Abbruch des Branch-and-Bound Verfahrens, wenn die prozentuale Abweichung ∆ der bisher besten gefundenen zulässigen Lösung z von der oberen Schranke z (Maximierungsproblem; bei Minimierung: Abweichung von unterer Schranke) nicht größer als ∆% ist (Gütegarantie)

Besonders hier: Achtung beim Updaten der Schranken (Auswirkungen auf Δ!) Am Beispiel eines Min-Problems (analog dazu das Max-Problem): die Upper Bound wird dann geupdatet, wenn Fall 1 eintritt und somit eine (bessere) feasible integer Lösung während des B&B Verfahrens auftritt. Allerdings kann auch die lower bound geupdatet werden: Dies geschieht in folgenden Fällen:

•

•

MUB/MLB: Während des B&B sind die ZF-Werte aller Problems bekannt. Aufgrund der Eigenschaft, dass durch Branching entstandene Probleme nie einen besseren ZF-Wert besitzen werden als die Probleme, die aus denen sie entstanden sind, kann die lower bound auf den niedrigsten ZFWert aller verbleibenden Probleme geupdatet werden, da dieser im folgenden Verlauf des Verfahrens nie unterschritten werden wird. Da bei MUB/MLB immer die ZF-Werte aller verbleibenden Probleme bekannt sind, wird die lower bound bei jedem Schritt geupdatet! • LIFO/FIFO: Während des B&B können (wenn dann, meist relativ am Anfang) die ZF-Werte aller Problems bekannt sein, müssen aber nicht (in den meisten Fällen sind nie alle ZF-Werte bekannt)! Aufgrund der Eigenschaft, dass durch Branching entstandene Probleme nie einen besseren ZF-Wert besitzen werden als die Probleme, die aus denen sie entstanden sind, kann die lower bound auf den niedrigsten ZF-Wert aller verbleibenden Probleme geupdatet werden, da dieser im folgenden Verlauf des Verfahrens nie unterschritten werden wird, aber nur wenn zufällig durch den Verlauf des B&B die ZF-Werte aller verbleibenden Probleme bekannt sind!

→ Dies wird vor allem relevant, wenn der Truncated B&B durchgeführt wird, da das Verfahren damit eventuell früher terminiert und eventuell auch ein kleineres Δ und damit eine größere Gewissheit über die Qualität der Lösung möglich wird! Branch-and-Bound bei binären Programmen Bestimmung der oberen Schranke: Sortierung der Projekte nach absteigendem relativen Wertbeitrag (relativer Wertbeitrag = 𝑁𝑢𝑡𝑧𝑒𝑛/ 𝐾𝑜𝑠𝑡𝑒𝑛) → Realisierung von Projekten (auch anteilig), wie es das Budget zulässt Bestimmung der unteren Schranke: Sortierung der Projekte nach absteigendem Wertbeitrag → Auswahl von Projekten, bis kein Projekt mehr ganz auswählbar ist Verzweigen: - Projekt ganz durchführen xi = 1 - Projekt nicht durchführen xi = 0...