KAPITEL 5 ENTSCHEID · PDF file5.1 Branch & Bound-Verfahren Seite 91 Die Teilung des Problems wird beim Branch & Bound in Falle der Lösung ganzzahliger Probleme dadurch vorgenommen

5 Entscheidungsbaumverfahren Seite 89

KAPITEL 5 ENTSCHEIDUNGSBAUMVERFAHREN

Ganzzahlige Probleme gehören häufig zur Klasse der sog. kombinatorischen Problemen, wozu man auch alle transformierten Modelle zu zählen hat:

! Reihenfolgeproblem Dabei sind n Elemente einer Menge in eine optimale Reihenfolge zu bringen. Theoretisch gibt es n! Reihenfolgen, mithin im allg. sehr, sehr viele. Zu dieser Klasse gehört z.B. das Travelling Salesman Problem und das Maschinenbelegungsproblem.

! Zuordnungsproblem

n Elemente einer Menge sollen je einem der n Elemente einer anderen Menge optimal zugeord-net werden. Auch hier gibt es maximal n! Zuordnungen. Jedoch ist das Problem als lineares Modell wegen seiner speziellen Struktur nicht lösbar

! Auswahlproblem

Aus einer Menge von n Elemnten soll eine Untermenge von m Elementen ausgewählt werden.

Es gibt theoretisch nm

Möglichkeiten. Das sog. Knapsack-Problem gehört zu dieser Klasse.

Gerade diese Probleme, ganz allgemein jedoch fast alle ganzzahligen Probleme haben i.d.R. außer-ordentlich viele zulässige Lösungen. Die fehlende Stetigkeitseigenschaft der Lösungsmannigfaltig-keit, d.h. die Diskretheit der Lösungen, erschweren die sog. implizite Enumeration. Darunter ist das Ausscheiden solcher Lösungen zu verstehen, die aufgrund bestimmter Eigenschaften nicht optimal sein können, weshalb sie nicht berechnet, d.h. explizit enumeriert zu werden brauchen. Es ist ein-leuchtend, daß eine Methode umso effizienter ist, je mehr Lösungen implizit berücksichtigt werden können, oder - was im gewissen Sinne gleichbedeutend ist - je weniger Lösungen explizit untersucht werden müssen.

Bei einem LP-Problem werden beispielsweise alle (unendlich viele) Lösungen untersucht, jedoch braucht nur ein Bruchteil der Eckpunkte explizit enumeriert zu werden. Die Mehrzahl aller Lösun-gen wird implizit auf der Basis bestimmter Eigenschaften (Konvexität, Linearität) einbezogen.

Eine ähnliche Vorgehensweise ist auch bei der Lösung von ganzzahligen Problemen anzustreben, jedoch - das sei vorausgeschickt - es ist ungleich schwerer zu erreichen. Ein Grund hierfür ist, daß häufig sehr viele Lösungen "gleichberechtigt" oder zumindest annähernd gleich gut sind, so daß es schwierig ist, einzelne (möglichst viele) durch andere zu dominieren. Das heißt, wegen der gegen-seitigen Nähe und der Vielzahl der Lösungen sind letztlich sehr viele Lösungen zu untersuchen, bevor man sicher sein kann, wirklich die günstigste Entscheidungsalternative gefunden zu haben. Im schlimmsten Fall kann das sogar bedeuten, daß man alle Lösungen enumerieren muß. Bei O(n!) Lösungen ist dies in vielen Fällen jedoch ein schier aussichtloses Unterfangen.

Dennoch ist es zweckmäßig, das Prinzip der Enumeration, d.h. der geordneten Entwicklung der Lösung beizubehalten. Hierfür bietet das graphische Modell des Baumes eine ausgezeichnete Strukturierungshilfe, wobei der Lösungsprozeß i.d.R. in der Wurzel begonnen wird und jede weitere Information zu einem Wachstum des Baumes führt. Jede Zustandsänderung bewirkt also das Hin-zufügen eines Zweiges, das ist graphentheoretisch eine Kante und ein Knoten. Auf diese Weise ent-steht eine Baumstruktur als Modell des Lösungsprozesses - im Gegensatz zum Graph als Modell des Realproblems.

Seite 90 5 Entscheidungsbaumverfahren

Von wesentlicher Bedeutung ist natürlich, wie das Wachstum des Entscheidungsbaumes abläuft, d.h. der Lösungsprozeß fortschreitet. Hierin und in der Art der Organisation unterscheiden sich die verschiedenen Entscheidungsbaumverfahren.

Ein trivialer Entscheidungsbaum ergibt sich natürlich, wenn man systematisch jede denkbare Lö-sung entwickelt und sie auf Zulässigkeit überprüft. Wegen der Vielzahl der Lösungen scheidet die vollständige Enumeration zur Lösung kombinatorischer Probleme aus.

Die wesentliche Idee ist nun zu versuchen, nur einenTeil der Lösungen explizit zu bestimmen und zu vergleichen. Nach Möglichkeit sollte dagegen der größere Teil der Lösungen durch intelligente, logische Überlegungen ausgeschlossen werden, wenn er für die optimale Lösung ohnehin nicht in Frage kommt. Im Prinzip folgt man also ähnlichen Überlegungen, die auch bei der Lösungen von LP-Problemem eine Rolle spielten.

Man versucht, einen möglichst großen Teil der Lösungen implizit zu enumerieren und man könnte, - mit Einschränkungen zwar - behaupten, je mehr Lösungen man implizit berücksichtigt, desto effi-zienter ist das Verfahren. Allerdings - und das ist die Einschränkung - darf man den Aufwand zur implizierten Berücksichtigung nicht vernachlässigen.

Die verschiedenen Entscheidungsbäume unterscheiden sich in:

! der Bedeutung der Komponenten "Knoten" und "Kanten" des Baums,

! der Organisation des Aufbaus des Baumes und

! den zahlreichen Möglichkeiten der Verzweigungen.

Diese mehr strategischen Entscheidungen haben zur Folge, daß die Lösung eines Problems dem Prinzip nach auf unterschiedliche Wegen eingekreist wird. Entsprechend definieren diese Unter-schiede auch jeweils Lösungsprinzipien.

Für einen konkreten Problemtyp müssen dann noch weitere Entwurfsentscheidungen getroffen wer-den, wie im Einzelfall vorgegangen wird. Es handelt sich dann um die Entwicklung oder Anwen-dung sog. Entscheidungsbaum-Verfahren.

Die verschiedenen Entscheidungsbaumverfahren unterscheiden sich im wesentlichen darin, wie der Baum aufgebaut und abgearbeitet wird, und was den Knoten und Kanten des Baumes zugeordnet wird. Dabei haben sich drei Lösungsprinzipien entwickelt:

⇒ Dynamische Optimierung

⇒ Begrenzte Enumeration

⇒ Branch & Bound

Letzteres Prinzip, das wohl auch die wirksamste aller Strategien enthält, wollen wir zur Lösung von ganzzahligen Problemen einsetzen.

5.1 Branch & Bound-Verfahren

'Branch & Bound' heißt wörtlich übersetzt 'Verzweigen - und - Abschätzen'. Gemeint ist damit die uralte Lösungsstrategie des 'divide - and - conquer', d.h. des 'Teilen - und - Besiegens'. Was zu stark, zu groß, zu schwer ist, um es als Ganzes zu bezwingen, wird in kleinere Einheiten aufgeteilt, die jede für sich untersucht werden, ob sie 'besiegbar' sind, d.h. die (bzw. eine) Lösung des Problems enthalten. Da ein Problem selten schon dadurch leichter lösbar wird, daß man es verkleinert, ver-sucht man zusätzlich abzuschätzen, ob in ihm überhaupt noch eine Lösung enthalten sein kann.

5.1 Branch & Bound-Verfahren Seite 91

Die Teilung des Problems wird beim Branch & Bound in Falle der Lösung ganzzahliger Probleme dadurch vorgenommen, daß der zulässige Lösungsbereih systematisch verkleinert wird. Man erhofft hiervon übersichtliche Lösungsmengen, die weiteruntersucht werden.

Das Abschätzen erfolgt fast immer dadurch, daß man statt des ganzzahligen Problems ein sog. rela-xiertes Problem löst. 'Relaxieren' heißt 'außer Kraft setzen'. Bei ganzzahligen Problemen wird fast immer die Ganzzahligkeitbedingung außer Kraft gesetzt, so daß ein größerer Lösungsraum entsteht, über dem die Zielfunktion im Maximum nun auch einen größeren Zielfunktionswert annehmen kann. Man gewinnt damit also eine Abschätzung, im Falle der Mximierung also eine obere Schran-ke.

Entscheidend ist nun, welche Schlüsse man aus den Schranken zieht.

⇒ Enthält das relaxierte Problem keine Lösung, so ist auch das ganzzahlige unlösbar.

⇒ Ist die Schranke kleiner als eine bekannte Lösung des ganzzahligen Problems, so kann keine bes-sere enthalten sein.

⇒ Ist schließlich die Lösung im Sinne des ganzzahligen Problems zulässig, so vergleicht man diese mit der besten bekannten zulässigen Lösung und ersetzt diese gegegebenfalls.

In allen drei Fällen braucht das Teilproblem nicht weiter untersucht zu werden. Man wählt daher ein anderes Teilproblem aus und wiederholt den Prozeß bis man über alle Teilprobleme eine der drei obigen Informationszustände erreicht. In diesem Fall hat man mit der besten bekannten zulässigen Lösung die Optimallösung des Gesamtproblems. Explizit enumeriert wurden dabei nur die ganzzah-ligen Lösungen der Teilprobleme, die sich im Laufe des Entscheidungprozesses als zulässig heraus-gestellt haben. Alle anderen Lösungen wurden von der jeweils besten bekannten Lösung dominiert und damit implizit berücksichtigt. Dies ist praktisch der Nachweis der Optimalität.

5.2 Das Branch & Bound-Prinzip

Nach dem zunächst relativ allgemein erläuterten Prinzip soll die grundsätzliche Vorgehensweise an einem Problem der ganzzahligen Optimierung illustriert werden. Wir werden es im weiteren das IP-Problem nennen.

Die Lösungsschwierigkeiten resultieren in einem IP-Problem aus der Ganzzahligkeit für einzelne Variablen. Indem diese relaxiert, d.h. nicht gefordert wird, vergrößert man den Lösungsraum. Löst man also statt des IP-Problems seine LP-Relaxation, so ergibt sich für ein Maximierungsproblem notwendigerweise ein Zielfunktionswert, der nicht kleiner sein kann als derjenige des LP-Problems, so daß wir mit z0 als optimalem Zielfunktionswert der LP-Relaxation LP0 eine obere Schranke für die gesuchte Lösung zmax des IP-Problems IP0 erhalten: zmax ≤ z.

Falls die Lösung von LP0 den Ganzzahligkeitsbedingungen genügt, ist man fertig, denn in diesem Fall ist zmax = z0, und man hat die gesuchte Lösung gefunden.

In jedem anderen Fall ergibt sich für mindestens eine Variable, z.B. xr, ein nicht ganzzahliger Wert.

Das IP-Problem IP0, das schwer lösbar erscheint, wird nun in zwei oder mehr - nicht notwendiger-weise disjunkte (obwohl sie in fast allen Algorithmen disjunkt sind) - Teilprobleme aufgeteilt, von der man sich erhofft, daß sie leichter lösbar sind, weil bereits Vorentscheidungen getroffen sind. Für alle Teilprobleme (z.B. IP11, IP12, IP13 etc.) wird wieder die LP-Relaxation berechnet, d.h. es wer-den dieLP-Probleme LP11, LP12, LP13 etc. gelöst. Die Teilprobleme werden zusammen mit den LP-Relaxationen in die sog. Kandidatenliste eingestellt, die alle Teilprobleme enthält, über die noch nicht befunden wurde (vgl. Abb. 5.1).


Abb. 5.1: Erste Schritte des Branch & Bound-Prinzips

Bevor das Teilproblem in die Kandidatenliste übernommen wird, kann man bereits wichtige Tests durchführen, die man als Abbruchkriterien (engl. fathoming criteria) bezeichnet. Gemeint ist da-mit, daß der weitere Abbau des Entscheidungsbaums an dem zugehörigen Zweig abgebrochen wird.

Abbruchkriterium FC1

Besitzt die LP-Relaxation LPj eines IP-Problems keine Lösung - d.h. ist sie widersprüchlich -

, kann auch das IP-Problem IPj keine Lösung haben. Der Lösungsbereich ist leer: L(IPj) = ∅ .

Der entsprechende Zweig des Entscheidungsbaums braucht dann nicht weiter verfolgt zu werden.

Das zweite Abbruchkriterium setzt voraus, daß eine zulässige Lösung des IP-Problems bekannt ist: zlfd. Diese Lösung kann z.B. mit Hilfe einer Heuristik bestimmt worden sein, oder sie ist während des laufenden Lösungsprozesses ermittelt worden. Wir setzen also voraus, daß zlfd stets der Ziel-funktionswert der besten bekannten, zulässigen Lösung ist.

Abbruchkriterium FC2

Falls die Lösung der LP-Relaxation LPj schlechter ist als die bislang beste bekannte Lösung,

zj < zlfd, braucht der Zweig nicht weiterverfolgt zu werden..

In diesem Fall sind alle im IPj enthaltenen Lösungen als schlechter als die laufende Vergleichslö-sung; man sagt auch, alle Lösungen von LPj und folglich auch IPj werden von zlfd dominiert.

Der Zweig braucht schließlich nicht weiterverfolgt zu werden, wenn LPj eine zulässige Lösung im Sinne des IPj hat.

Abbruchkriterium FC 3

Falls die Lösung der LP-Relaxation LPj zulässig bezüglich IPj ist, d.h. die (relaxierten)

Ganzzahligkeitsbedingungen erfüllt, wird geprüft, ob diese besser ist als die beste bekante Lö-

sung: zj > zlfd.. Wenn ja, wird sie neue Vergleichslösung.

IP0

LP0: z0

IP11

LP11: z11

IP12

LP12: z12

IP13

LP13: z13

Branching = Verzweigen

Bounding = Beschränken Kandidatenliste{or3ab501.pre}

5.2 Das Branch & Bound-Prinzip Seite 93

In jedem Fall braucht der Zweig nicht weiter verfolgt zu werden, da jede andere ganzzahlige Lösung im IPj notwendigerweise schlechter (oder höchstens gleich gut) ist.

Falls keines der drei Abbruchkriterien wirksam wird, kommt das Teilproblem in die Kandidatenlis-te, aus der dann ein Kandidatenproblem ausgewählt wird, um weiter aufgespalten zu werden: wel-ches damit die Kandidatenliste verläßt, hängt von entsprechenden Kriterien ab. Üblicherweise wählt man das Problem IPk, dessen LP-Zielfunktionswert zk maximal ist, weil man damit das Problem auszusuchen hofft, bei dem die größte Chance zu bestehen scheint, eine gute Lösung zu finden. Ver-folgt man den Aufbau und die Wirkung der Abbruchkriterien weiter, so ergibt sich letztendlich ein Entscheidungsbaum gemäß Abb. 5.2 Das Problem ist gelöst, wenn eine zulässige Lösung gefunden wurde (zlfd) und die Kandidatenliste leer ist. In diesem Fall sind alle Endknoten des Baumes abgear-beitet.

Abb. 5.2: Ausbau des Entscheidungsbaums und Abbruch wegen verschiedener Kriterien

5.3 Ein Branch & Bound-Beispiel

Das Prinzip soll nun an einem numerischen Beispiel illustriert werden:

Problem IP = IP0

Max z

mit z = 21x1 + 11x2

u.d.N. 6x1 + 4x2 ≤ 15

x1,x2 ≥ 0 ganzzahlig

Löst man das Problem zunächst ohne Ganzzahligkeitsbedingung (LP-Relaxation), so ergibt sich:

IP0

IP11 IP12 IP12

LP0: z0

IP21 IP22 IP23IP24 IP25

IP31 IP32

LP11: z11 LP12: z12 LP13: z13

LP21: z21 LP22: z22 LP23: z23 LP24: z24 LP25: z25

LP31: z31 LP32: z32

FC1: L(LP13) =

FC1: L(LP24) = FC3: zlfd. = z23

FC3: zlfd. = z32

FC2: z25 < zlfd. FC2.

FC2.

or3ab502.pre}


Max x1 x2 RS Max x3 x2 RS

z0 −21 −11 0 z0 72 3 52 1

2

x3 6 4 15 x1 16 2

3 52

Tab. 5.1a-b: Lösung des Problems LP0

Wir registrieren:

! Die Lösung ist keine zulässige Lösung des IP0.

! Für die Lösung des IP muß somit gelten: zmax ≤ 52.

! Da der Wert von x1 nicht ganzzahlig ist, kann man schließen, daß im IP entweder x1 ≤ 2 oder x1 ≥ 3 gelten muß.

Indem man diese Restriktionen dem ursprünglichen Problem zufügt, ergeben sich zwei Teilproble-me. Das heißt, die Formulierung disjunkter Nebenbedingungen ergibt zwei Teilprobleme. Wir ha-ben hiermit eine Verzweigung durchgeführt:

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

z11 −21 −11 0 z11 21 −11 42 z11 92 11

4 50 14

x3 6 4 15 x3 −6 4 3 x2 − 32

14 3

4

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

Tab. 5.2a-c: Lösung des Problem LP11


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

Tab. 5.3a-b: Lösung des Problem LP12

Das Problem LP12 hat keine zulässige Lösung, d.h. L (LP12) = ∅ (FC1).

Das Problem LP11 wird in die Kandidatenliste gestellt. Der Entscheidungsbaum hat die Form von Abb. 5.10. Beide Probleme LP11 und LP12 umfassen zusammen alle ganzzahligen Lösungen, weil nur der Bereich 2 < x1 < 3 ausgeschlossen wurde, in dem bekanntlich keine ganzzahligen Lösungen liegen können.

5.3 Ein Branch & Bound-Beispiel Seite 95

Enthält alle (ganzzahligen) Lösungen.

Enthält alle ganzzahligen Lösungen.

Enthalten zusammen alle ganzzahligen Lösungen.

Abb. 5.3: Entscheidungsbaum 1

Das heißt, alle ganzzahligen Lösungen des IP sind garantiert im Knoten LP11 enthalten. Da jedoch die Variable x2 nicht ganzzahlig ist, werden hieraus wieder 2 Probleme gebildet:

LP21: x2 ≤ 0 → zusammen mit x2 ≥ 0 → x2 = 0:

Max x1 RS Max x1' RS

z21 −21 0 z21 21 42

x3 6 15 x3 −6 3

x1' 1 2 x1 1 2


LP21 hat eine ganzzahlige Lösung (FC3), d.h. die erste zulässige Lösung des IP ist gefunden: → zlfd = 42

LP22: x2 ≥ 1:


z22 −21 −11 0 z22 −21 −11 11

x3 6 4 15 x3 6 4 11

x1' 1 0 2 x1' 1 0 2

x4 0 −−−−1 −1 x2 0 −1 1

Tab. 5.5a-b: Lösung des Problems LP22 mit x2 ≥ 1

LP12 =

LP0: z0 = 52,5

x1 = 2,5; x2 = 0

x1 <= 2 x1 >= 3

LP11: z11 = 50,25

x1 = 2; x2 = 0,75 FC1

IP: max z A·x <= b ganzz. x >= 0

{or3ab503.pre}


Max x3 x4 RS

z22 72 3 49 1

2

x1 16 2

3 116

x1' − 16 − 2

3 16

x2 0 −1 1

Tab. 5.5c: Optimale Lösung des Problems LP22

Das Problem IP21 hat eine ganzzahlige Lösung, es braucht nicht weiter untersucht zu werden (FC3). Das Problem IP22 geht mit der Oberschranke z22 = 49 1

2 in die Kandidatenliste. Es ergibt sich also folgender Weiterbau zum Entscheidungsbaum 2 in Abb. 5.4.

LP22 derzeit einziges Problem in der Kandidatenliste.


Aus der Kandidatenliste wird das derzeit einzige Problem LP22 ausgewählt, und anhand der nicht ganzzahligen Variablen x1 wird verzweigt:

x2 = 0 x2 >= 1

x1 = 2; x2 = 0,75

LP21: z21 = 42

x1 = 2; x2 = 0

LP22: z22 = 49,50

LP11: z11 = 50,25

x1 = 11/6; x2 = 1

LP0

LP12

IP

x1 >= 3x1 <= 2

FC1

FC3 {or3ab504.pre}


LP31: x1 ≤ 1 ist restriktiver als x1 ≤ 2, es ersetzt also eine Nebenbedingung:.


z31 −21 −11 0 z31 −21 −11 11

x3 6 4 15 x3 6 4 11 x1' 1 0 1 x1' 1 0 1 x4 0 −−−−1 −1 x2 0 −1 1

Max x1' x4 RS Max x1' x3 RS

z31 21 −11 32 z31 92 11

4 45 34

x3 −6 4 5 x4 − 32 1

4 54

x1 1 0 1 x1 1 0 1 x2 0 −1 1 x2 − 3

2 14 2 1

4

Tab. 5.5a-d: Lösung des Problems LP31

LP32: x1 ≥ 2 → zusammen mit x1 ≤ 2 → x1 = 2:

Max x2 RS Max x4 RS

z32 −11 42 z32 −11 53

x3 4 3 x3 4 −1 ⇐ keine zuläss. Lösung

x4 −1 −1 x2 −1 1


Das Problem LP32 hat keine zulässige Lösung, so daß abgebrochen werden kann (FC1). Der Ent-scheidungsbaum 3 hat nun die Form von Abb. 5.5.



Das Problem LP31 aus der Kandidatenliste wird an der Variablen x2 weiter geteilt. In der folgenden Lösung muß man auch die Nebenbedingung x2 ≥ 1 berücksichtigen, d.h. eine Untergrenze für x2. Das geschieht dadurch, daß x2 auf die Untergrenze gesetzt und durch die Variable x2 substituiert wird. Gleichzeitig muß die Obergrenze um diesen Betrag, also 1, erniedrigt werden.

LP41: x2 ≤ 1:

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

z41 −21 −11 11 z41 21 −11 32 z41 21 11 43

x3 6 4 11 x3 −6 4 5 x3 −6 −4 1

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

x2' 0 1 1 x2' 0 1 1 x2 0 1 1

Tab. 5.7a-c: Lösung des Problems LP41: die Rücktransformation ergibt x2 = x2 + 1 = 2

x 2 = 0 x 2 > = 1

L P 3 1 : z 3 1 = 4 3 3 /4

x 1 = 1 ; x 2 = 2 1 /4

L P 2 2 : z 2 2 = 4 9 ,5 0

L P 3 2 :

x 1 = 1 5 /6 ; x 2 = 1

L P 0

L P 1 2

IP

x 1 > = 3x 1 < = 2

F C 1

L P 1 1

L P 2 1

x 1 < = 1 x 1 = 2

F C 1

{ o r3 a b 5 0 5 .p re }


LP42: x2 ≥ 3 mit x2 ≥ 1 → x2 ≥ 3

Max x1 x2 RS Max x1 x4 RS Max x3 x4 RS

z42 −21 −11 0 z42 −21 −11 33 z42 72 3 43 1

2

x3 6 4 15 x3 6 4 3 x1 16 2

3 12

x1' 1 0 1 x1' 1 0 1 x1' 1 −23 1

2

x4 0 −1 −3 x2 0 −1 3 x2 0 −1 3

Tab. 5.8a-c: Lösung des Problems LP42

Das Teilproblem LP41 hat eine ganzzahlige Lösung (FC3) mit einem Zielfunktionswert z41 = 43, der besser ist als zlfd = 42, so daß zlfd = 43 gesetzt wird und die Lösung von IP41 die neue Vergleichslö-sung ist.

Das Teilproblem LP42 hat einen Zielfunktionswert von z42 = 43 12 . Es kann also bestenfalls eine

ganzzahlige Lösung mit dem Wert 43 enthalten, also keine bessere als zlfd (FC2). Somit ergibt sich der Entscheidungsbaum 4 in Abb. 5.6.

Abb. 5.6: Vollständiger Entscheidungsbaum

Alle Zweige des Entscheidungsbaums sind nun abgearbeitet, so daß die letzte laufende Lösung die gesuchte maximale Lösung des IP ist: zmax = zlfd= 43 für x1 = 1 und x2 = 2.

x2 = 0 x2 >= 1

LP22

LP0

LP12

IP

x1 >= 3x1 <= 2

FC1

LP11

LP21

x1 <= 1 x1 = 2

FC1

LP32 LP31

LP42 LP41

FC2 FC3

FC3

x2 <= 2 x2 >= 3

{or3ab506.pre}


Die verschiedenen Verzweigungen, die jeweils durch zusätzliche Nebenbedingungen vorgenommen wurden, d.h. die Teilug des zulässigen Bereiches, läßt sich an Hand der Abb. 5.7 nachvollziehen.

Abb. 5.7: Aufteilung des zulässigen Bereiches beim Verzweigen

5.4 Zusammenfassende Diskusssion

! Mit dem Unterdrücken der Ganzzahligkeit bei der ersten Lösung geht keine ganzzahlige Lösung verloren, denn der zulässige Bereich wurde erweitert. D.h. alle Lösungen des IP sind auch zuläs-sige Lösungen des LP.

! Falls die Lösung des LP ganzzahlig wäre, wäre sie auch die optimale Löusng des IP gewesen.

! Bei der ersten Verzweigung - und das gilt für alle folgenden Verzweigungen sinngemäß - wurde der zulässige Bereich, d.h. die Menge aller Lösungen in Teilmengen aufgeliedert. Das Prinzip "Teile und Besiege" der Untersuchung einer Teilmenge kann bei jedem Problem angewendet werden. Löst man Teilprobleme und vergleicht man die Lösungen, so hat man auch das größere Problem gelöst, wenn man sicherstellt, durch die Aufteilung keine Lösung verloren zu haben.

! Bei der Bildung von Teilmengen bestehen relativ viele Freiheitsgrade. Es müssen lediglich zwei Bedingungen beachtet werden:

⇒ keine potentielle Lösung darf verloren gehen

⇒ die bisher bekannte - nicht zulässige - Lösung muß ausgeschlossen werden (vgl. → Bedin-gungen an Schnittebenen)

! Durch die Teilmengenbildung sind die Probleme i.d.R. eingeschränkter - es sind Informationen hinzugekommen. Selten sind sie jedoch wirklich leichter lösbar geworden, d.h. weniger kom-

2

2

1

1

3 x1

x2

o

3

4

4

LP12

LP11

LP22

LP31

LP41

LP42

Zielfunktion

{or3ab507.pre}

5.4 Zusammenfassende Diskussion Seite 101

plex. (Ein ganzzahliges Problem ist immer schwer lösbar, auch über einen etwas kleineren Lö-sungsbereich)

⇒ Um dennoch an mehr Information über die Lösungen zu gelangen, versucht man nun abzu-schätzen, welche Lösungen überhaupt noch in Frage kommen. Eine der mächtigsten Ab-schätzungsmöglichkeiten ergibt sich durch Relaxation, d.h. durch Stillegung bestimmter Ein-schränkungen.

⇒ Typischerweise werden diejenigen Bedingungen relaxiert, die für die Lösung am schwierigs-ten sind.

Als Folge der Relaxation ergibt sich ein vergrößerter Lösungsbereich. Somit stellt die Lösung der Relaxation für ein Maximierungsproblem stets eine Oberschranke und für ein Minimie-rungsproblem stets eine Unterschranke dar.

! Die derart gewonnene Lösung kann nun im Sinne des ersten Punktes als Untersuchung eines Teilproblems angesehen werden. Das heißt, der Prozeß wiederholt sich für das Teilproblem. Es liegt eine rekursiver Prozeß vor.

! Wenn dieser rekursive Prozeß festgesetzt wird, werden zum Schluß eine große Zahl von Knoten gebildet worden sein: bei vollständiger, expliziter Enumeration für jede zulässige Lösung auch Endknoten.

Da dies mit Sicherheit zu aufwendig wäre, muß man sich Gedanken machen, ob man einzelne Teilprobleme nicht mehr weiter zu untersuchen braucht.

! Im vorliegendem Fall ist festzustellen:

⇒ Falls eine Teilproblem keine zulässige Lösung besitzt (FC1)

⇒ Falls die optimale Lösung eines Teilproblems eine zulässige Lösung des Gesamtproblems ist (FC2)

⇒ Falls die optimale Lösung eines Teilproblems nicht besser ist als die beste bekannte zulässige Lösung (FC3)

! Mit dem Entscheidungsbaum soll angestrebt werden:

⇒ alle Lösungen zu erfassen,

⇒ jedoch möglichst viele durch mathematische oder logische Deduktion, d.h. implizit zu enu-merieren,

⇒ bzw. möglichst frühzeitig zu erkennen, daß die in einem Teilproblem enthaltenen Lösungen nicht optimal sein können.

! Das beschriebene Entscheidungsbaum-Verfahren ist das "Branch and Bound"-Verfahren von Dakin. Es ist ein Entscheidungsbaum-Verfahren, entwickelt für eine bestimmte Klasse von Problemen. Ein anderes ebenfalls für MIP-Probleme geeignetes Verfahren ist das von Land und Doig.

5.5 Vor- und Nachteile von Branch & Bound-Verfahren

Nachdem die grundsätzliche Vorgehensweise beschrieben ist, sollen kurz die Vorteile der Branch & Bound-Methode diskutiert werden.

☺ Anbindung an LP-Modul


Branch & Bound kann relativ einfach als Modul an ein existierendes LP-Programm angefügt werden.

Die LP-Probleme benachbarter Knoten im Baum unterscheiden sich letztlich nur in einem Bound. Ausgehend von der Optimalbasis des unmittelbaren Vorgängers können daher schnell die Optimalbasen der neuen Teilprobleme berechnet werden. Dennoch sollte der Lösungsauf-wand für die LP-Probleme nicht unterschätzt werden. Es können Vorkehrungen getroffen werden, solche Knoten zunächst zurückzustellen, die zu viel Rechenaufwand benötigen.

☺ Gestaltungsfreiheit des Algorithmus

Der Aufbau des Baumes und die Suchstrategie bieten für den Benutzer ein Höchstmaß an Freiheitsgraden.

Das bedeutet, daß drei der vier Basisentscheidungen (Knotenauswahl, Verzweigen, Lösen des Teilproblems) i.d.R. noch viele Wahlmöglichkeiten bieten. Der wesentliche Unterschied der MIP-Codes besteht darin, wie dieser Spielraum ausgefüllt wird, und wie diese Freiheitsgrade vom Benutzer problemabhängig ausgenutzt werden können.

☺ Heuristische Unterstützung

Die Auswahlentscheidungen (Verzweigungsknoten, Verzweigungsvariable) können durch sinnvolle Prioritätsregeln unterstützt werden.

Die auf heuristischen Prinzipien basierenden Prioritätsregeln bilden die wesentlichen Baustei-ne eines MIP-Codes. Die Wahl des 'richtigen' Knotens und die Entscheidung, an welcher Va-riablen verzweigt wird, entscheidet letztlich über die Tiefe und die Breite des Baumes, d.h. über den Lösungsaufwand. Ferner hängt es ganz wesentlich von diesen Entscheidungen ab, wie schnell man 'gute' IP-Lösungen findet, die ihrerseits mächtige Schranken darstellen.

☺ Verwendbarkeit der Lösung bei Abbruch

Der Benutzter verfügt mit jeder IP-Lösung, deren Optimalität noch nicht nachgewiesen ist, mindestens über eine untere Schranke im Minimierungsfall (eine obere Schranke beim Maxi-mierungs-Problem), anhand derer er seine beste Lösung beurteilen kann.

Die in der Kandidatenliste verbliebenen Knoten können nur noch Lösungen enthalten, deren Funktionswert zwischen dem besten Wert zj der restlichen Knoten und der bekannten IP-Lösung zlfd liegen. Ist der Abstand |zj - zlfd| gering, so ist die Wahrscheinlichkeit groß, daß zlfd maximal ist oder mindestens nahe am Optimum liegt. Zum Nachweis der Optimalität müßte der Entscheidungsbaum vollständig abgearbeitet werden. Auf diesen, in den meisten Fällen sehr aufwendigen Prozeß kann dann u.U. verzichtet werden, wenn man nicht unbedingt die optimale Lösung berechnen muß bzw. auf den Nachweis der Optimalität verzichten kann.

Den mannigfaltigen Vorteilen des Branch & Bound stehen jedoch auch gewichtige Nachteile gegenüber.

# Hoher Speicheraufwand

Die größten Schwierigkeiten ergeben sich aus dem i.d.R. enorm hohen Speicheraufwand-

Die Verwaltung der erwähnten Kandidatenliste erfordert einen hohen Grad an Datenorganisa-tion, wobei folgende Informationen vorgehalten werden müssen:

5.5 Vor- und nachteile von Branch & Bound-Verfahren Seite 103

⇒ Der Entscheidungsbaum selbst muß abgebildet werden, damit nachvollziehbar wird, wel-che Restriktionen für die Verzweigung verwendet wurde.

⇒ Jedes Blatt, d.h. jeder in die Kandidatenliste aufgenommene Knoten enthält eine vollstän-dige LP-Relaxation, dessen optimale Lösung festgehalten wird (Basis, Variablen). Auf die-se Lösung muß im Fall derAuswahl und des Verzweigens 'aufgesetzt' werden, so daß hier-aus durch Reinversion und Upper-Bounding-Technik mit möglichst geringem Aufwand die neue Lösung berechnet werden kann.

⇒ Da die Anzahl der zurückgestellten Knoten i.allg. sehr groß wird, ergibt sich ein hoher Suchaufwand (information retrieval).

# Rechenaufwand

Durch die wiederholte Lösung vieler LP-Probleme ergibt sich ein hoher Rechenaufwand.

Ein für die 'Zu-Fuß-Rechnung' scheinbar großes Problem, das der wiederholten Lösung der LP-Relaxation, sei zwar erwähnt; es stellt sich jedoch als eher unwesentlich heraus, da der Schritt von der Optimallösung des Vorgangsknotens zur neuerlichen Lösung i.d.R. nur wenige Iterationen (häufig nur eine) bedeutet.

# Variable Problemgröße

Unangenehm ist auch, daß die Problemdimension, d.h. im wesentlichen die Anzahl der Ne-benbedingungen und damit die Basisgröße, nicht konstant ist.

Das erschwert eine optimale Datenverwaltung in Listenform, weil die Einträge pro Knoten un-terschiedliche Längen besitzen. Andererseits sind die hinzu kommenden Nebenbedingungen grundsätzliche Bounds, die wiederum einfach zu verwalten sind.

Die Vor- und Nachteile der Branch & Bound-Verfahren gegeneinander aufrechnen, macht wenig Sinn. Wesentlicher ist, sie mit alternativen Verfahren, z.B. dem Schnittebenenverfah-ren, zuvergleichen. Dann allerdings schneiden Branch & Bound-Verfahren günstiger ab, weil sie sich bei den kritischen Punkten, Rundungsfehler und langsame Konvergenz, besser verhal-ten.

Nicht gering schätzen darf man die 'primale Natur' der Branch & Bound-Verfahren, die auch beim Abbruch eine zulässig Lösung liefern. Bei schwierigen, schlecht strukturierten Proble-men kann es durchaus zu Lösungszeiten kommen, die im Bereich mehrerer Stunden liegen. Es ist dann äußerst ärgerlich, wenn man wegen einer Zeitbeschränkung oder wegen zu großer Rundungsfehler "aussteigt", ohne wenigstens eine zulässige Lösung zu kennen. Bei der An-wendung des Branch&Bound hat man dann zumindest die Lösung zlfd, die häufig bereits die optimale Lösung ist, für die lediglich der Nachweis der Optimalität noch nicht vollständig ge-führt wurde.

5.6 Entwurfsentscheidungen beim Branch & Bound

In der Abb. 5.8 ist ein allgemeines Ablaufschema wiedergegeben, das von Geoffrion und Marsten1 für alle Algorithmen der ganzzahligen Planungsrechnung entwickelt wurde. Es enthält 12 Schritte,

1 Geoffrion, A.M.; Marsten, R.E.: Integer Programming Algorotithmus: A Framework and State-of-the-Art Survey, in:

Management Science, 18, No. 9, May 1972


die im einzelnen zuvor bereits beschrieben, kommentiert und anhand des Beispiels illustriert wor-den waren. Daher spricht das Flußdiagramm weitgehend für sich, und es sollen lediglich einige Be-merkungen zu den einzelnen Schritten angefügt werden:

Schritt 1: Vorkenntnisse über das zu lösende Problem (MIP) können zu Informationen über eine relativ gute Schranke z0 führen. Je besser diese ausfällt, desto weniger lang wird die Kandiatenliste. Heuristiken könnten z.B. verbesserte Schranken liefern.

Abb. 5.8: Allgemeines Ablaufschema der Algorithmen der ganzzahligen Planungsrechnung

Schritt 3: Verschiedene Regeln zur Auswahl des Kandidatenproblems können den Enumeration-sablauf erheblich beeinflussen. 'Last-In-First-Out' (LIFO) wurde das jeweils letzte Prob-lem zum Verzweigen wählen, d.h. die Buchhaltung des Baumes könnte stark vereinfacht werden. Jedoch würde man dabei den Zielfunktionswert zur Steuerung des Enumerati-

FC1:L(LPk) = ?

Beginn STOP

Initiiere Kan-didatenliste

Wähle Kandida-tenproblem IPk

Relaxiere IPk

=> LPk

Löse LPk

FC2: zk <= zlfd ?

FC3: Ist zk zulässig?

Weiter mit LPk?

ModifiziereRelaxation

Teile IPk

Aktualisiere fallsmöglich zlfd

Liste leer?Nein

Ja

Nein

Ja

Nein

Ja

Nein

Ja

Nein

Ja

12

11

10

9

8

7

6

5

432

1

{or3ab508.pre}

5.6 Entwurfsentscheidungen beim Branch & Bound Seite 105

onsprozesses ganz außer acht lassen. Z.B. würde man darauf verzichten, möglichst früh eine besonders gute Lösung finden zu können - dies bliebe dem Zufall überlassen. Line-are Prioritätsregeln könnten in der Kandidatenliste Probleme nach ganz gezielten Ge-sichtspunkte (z.B. größter Zielfunktionswert, Anzahl ganzzahliger Variablen, o.ä.) an-gewendet werden. Das setzt jedoch eine viel aufwendigere Auswahl und entsprechende Buchhaltung voraus.

Schritte 4 und 5: Die Relaxation und anschließende Lösung sollte einerseits gute Schranken liefern und andererseits leicht durchführbar sein. Auch hier ist zusätzlicher Aufwand vorstell-bar, um schärfere Schranken zu erhalten. Beispielsweise kann man Schnittebenen ein-führen, so daß die Wahrscheinlichkeit wächst, nah-optimale Lösungen zu finden.

Schritte 6 bis 8: Die Abbruchkriterien sind oben beschrieben.

Schritt 10: Konnte das Problem nicht ausgeschieden werden, so kann man durch Modifikation der Relaxation (→ Schnittebenen!) eventuell eine verbesserte Schranke und damit eine er-höhte Chance des Abbruchs erhalten.

Schritt 11: In diesem allgemeinen Ablaufschema wird nach der Untersuchung des Kandidatenprob-lems dieses aufgeteilt (Verzweigung), und beide Probleme kommen in eine Kandidaten-liste.

Schritt 12: Sobald eine verbesserte Lösung gefunden wurde und die laufende beste Lösung zlfd aktualisiert ist, können die Probleme in der Kandidatenliste mit dieser verglichen wer-den. Kleinere Schranken zj < zlfd führen zum Ausschluß aus der Kandidatenliste, so daß die Liste u.U. mit einem Schlag stark verkleinert werden kann.

Das Branch & Bound-Prinzip beruht auf dem Aufbau und der Abarbeitung eines Entscheidungs-baumes, der nichts anderes als ein Strukturierungs-Modell als Lösungsprozeß darstellt. Während das Netzwerk oder der Basisbaum darin eine Abbildung des Realproblems darstellt, ist hier der Baum Hilfsmittel zur Darstellung und zum Ordnen des Lösungsganges. Je nach Bedeutung von Knoten und Kanten des Entscheidungsbaumes und nach der Organisation des Aufbaus und Abarbei-tung unterscheidet man verschiedene Prinzipien: ! Branch &Bound ! Dynamische Programmierung ! Begrenzte (implizite) Enumeration

Die Tab. 5.9 gibt eine kurze Übersicht über die Charakterisika der verschiedenen Prinzipien.

Bedeutung von Branch & Bound Dynamische Prog. Begrenzte Enumeration

Knoten Teilproblem mit voll-ständigen Lösungen

Teillösungen

(also unvollständig)

Teillösungen

(unvollständig)

Kanten Zustandsänderung durch Teilung der

Lösungsmenge

Zustandsänderung zum Zweck der Vervoll-

ständigung der Lösung

Zustandsänderung zum Zweck der Vervoll-

ständigung der Lösung

Organisation gemischt (parallel, sequentiell)

streng parallel (in die Breite)

sequentiell, um rasch eine vollständige Lö-

sung zu erhalten

Tab. 5.9: Charakteristika von Entscheidungsbaumverfahren


Um ein konkretes Problem zu lösen, müssen dann letztlich die verschiedenen Schritte des Ablauf-schemas (Abb. 5.8) durch konkrete Realisationen und Regeln ausgestaltet werden, d.h. man muß letztendlich befinden:

• Wo (im Baum) soll fortgefahren werden?

• Wie soll verzweigt werden?

• Wie findet man eine Schranke?

• Wann soll abgebrochen werden?

Die am Beispiel in Abschnitt 5.3 vollzogenen Entscheidungen wurden von Dakin zur Lösung von MIP vorgeschlagen. Es ist abschließend algorithmisch zusammengefaßt.

5.7 Branch & Bound-Algorithmus von Dakin

Das Verfahren von Dakin ist der Kern aller MIP-Software-Programme. Es wird im folgenden für ein Maximierungsproblem beschrieben.

Branch & Bound-Verfahren von Dakin

Input: Gemischt ganzzahliges Problem (MIP)

Output: zmax, xmax2

Voraussetzung: LP-Relaxationen sind in Kandidatenliste gespeichert. Die Auswahl wird nach der großen Schranke (zj) vorgenommen.

Schritt 1: Initialisierung

Löse die LP-Relaxation LP0 des Gesamtproblems: z0, x0.

Falls die Lösung zulässig ist, ist die MIP-Lösung gefunden und die Rechnung ist beendet.

Andernfalls füge LP0 der Kandidatenliste zu, setze zllfd = 0 (oder einer bekann-ten, besseren Schranke) und gehe nach Schritt 2.

Schritt 2: Wahl des Kandidatenproblems LPk

Wähle aus der Kandidatenliste ein Kandidatenproblem, z.B. durch

{ }z zj

jk = max und gehe nach Schritt 3.

Falls die Kandiatenliste leer ist, ist zmax = zlfd und xmax = xlfd, Stop.

Schritt 3: Verzweigen (Branching)

3.1 Wähle eine ganzzahlige Variable, die in der Lösung nicht ganzzahlig ist, z.B. die Variable xr, die von der Ganzzahligkeit am weitesten entfernt ist:

x x fr r r= + mit { }f fri

i= max

3.2 Bilde das Nachfolgeproblem zu LPk, indem die Grenzen

2 Die Variable ist hier fett gedruckt, weil darunter der ganze Lösungsvektor zu verstehen ist.

5.7 Branch & Bound-Algorithmus von Dakin Seite 107

x x x xr r r r≤ ≥ +bzw. 1 eingeführt werden.

3.3 Füge jeweils eine Schranke dem Problem LPk hinzu,

es entstehen die beiden Nachfolgerprobleme: LPk,1 und LPk,2.

3.4 Passe die neue Nebenbedingung der Optimallösung von LPk an, und löse das entstandene Problem.

Schritt 4: Abbruch (Bounding)

Verwirf das Problem LPk,i, falls

4.1 L (LPk,i) = ∅ , d.h. LPk,i keine zulässige Lösung besitzt (FC1).

4.2 zk,i ≤ zlfd, d.h. die Schranke zk,i bereits schlechter ist als die beste bisher bekann-te Lösung (FC2).

4.3 zk,i, xk,i, zulässig sind. Ist zk,i ≤ zlfd, verfahre wie unter 4.2. Falls zk,i > zlfd, setze zlfd = zk,i und xlfd = xk,i (FC3).

In allen anderen Fällen wird LPk,i in die Kandidatenliste übernommen. Gehe nach Schritt 2.

Algorithmus 5.1: Branch & Bound-Verfahren nach Dakin

Bei binären Problemen (0-1) vereinfacht sich das Verfahren insofern, als bei Einführung kontinuier-licher Grenzen 0 ≤ xj ≤ 1 bei Nichtganzzahligkeit nur die beiden Bedingungen xj = 0 oder xj = 1 denkbar sind. Diese Alternativen sind dann die Verzweigungen, so daß in der entsprechenden opti-malen Lösung, aus der die Nachfolgerprobleme generiert werden, die Variable xj. auf die Werte 0 oder 1 fixiert wird.


5.7 Branch & Bound-Algorithmus von Dakin Seite 109

KAPITEL 5 ENTSCHEIDUNGSBAUMVERFAHREN ....................................................... 89

5.1 Branch & Bound-Verfahren................................................................................................................................90

5.2 Das Branch & Bound-Prinzip..............................................................................................................................91

5.3 Ein Branch & Bound-Beispiel .............................................................................................................................93

5.4 Zusammenfassende Diskusssion ........................................................................................................................100

5.5 Vor- und Nachteile von Branch & Bound-Verfahren .....................................................................................101

5.6 Entwurfsentscheidungen beim Branch & Bound.............................................................................................103

5.7 Branch & Bound-Algorithmus von Dakin ........................................................................................................106

Documents

KAPITEL 5 ENTSCHEID · PDF file5.1 Branch & Bound-Verfahren Seite 91 Die Teilung des Problems wird beim Branch & Bound in Falle der Lösung ganzzahliger Probleme dadurch vorgenommen