I

Inhaltsverzeichnis

  Abbildungsverzeichnis  II

Tabellenverzeichnis III   

  Abkürzungsverzeichnis  IV

1  Abgrenzung der Themenstellung  1

2  Binary Integer Programming (BIP)  2

2.1  Probleme in der Praxis  2

2.1.1  Planung fixer Investitionen  3

2.1.2  Standortauswahl  3

2.1.3  Terminplanung für zusammenhängende Aktivitäten  4

2.2  Allgemeines Optimierungsmodell  5

2.3  Berechnungsschwierigkeiten  6

2.4  Lösungsalgorithmen im Überblick  7

3  Branch-and-Bound (B&B) zur Lösung von BIP-Problemen  9

3.1  Lösungsschritte  9

3.1.1  Initialisierung (Iteration 0)  10

3.1.2  Branching  10

3.1.3  Bounding  11

3.1.4  Sondierung  11

3.1.5  Optimalitätstest  12

3.2  Lösung eines Rucksackproblems  12

3.3  Alternative Techniken  17

3.3.1  Modellierungstechnik  17

3.3.2  Techniken der Initialisierung (Iteration 0)  17

3.3.3  Branching-Techniken  18

3.3.4  Bounding-Techniken  20

3.4  Das Softwarewerkzeug „LPSolve“  20

4  Bewertung  22

  Literaturverzeichnis  23

II

  Abbildungsverzeichnis  

2.1  Problemgruppen der kombinatorischen Optimierung  2

2.2  Klassifikation von Lösungsalgorithmen nach deren Lösungsgüte  7

3.1  Verzweigung eines BIP-Teilproblems in zwei neue BIP-Teilprobleme  11

3.2  Rucksackproblem - Iteration 0  14

3.3  Rucksackproblem - Iteration 1  15

3.4  Rucksackproblem - Iteration 2  15

3.5  Rucksackproblem - vollständiger Lösungsbaum  16

  3 6 Rucksackproblem in LPSolve  21

III

  Tabellenverzeichnis  

2.1  Lösungsmengen eines BIP-Modells für verschiedene Eingabegrößen  6

  3 1 Beispielwerte für ein Rucksackproblem  13

IV

Abkürzungsverzeichnis

B&B Branch and Bound

BIP Binary Integer Programming

GUI Graphical User Interface

IDE Integrated Development Environment

IP Integer Programming

LIFO Last In - First Out

LP Linear Programming

MCS Multiple Choice Situation

MILP Mixed Integer Linear Programming

MIP Mixed Integer Programming

MLB Minimum Lower Bound

MUB Maximum Upper Bound

OR Operations Research

PIP Pure Integer Programming

SOS Special Ordered Sets

TP Teilproblem

1 1 ABGRENZUNG DER THEMENSTELLUNG

1 Abgrenzung der Themenstellung

Reale Entscheidungsprobleme bilden den Hintergrund des Fachgebietes „Operations Research“ (OR). Die Abbildung dieser Probleme als Modelle und die Entwicklung bzw. Anwendung von Algorithmen zu deren Lösung sind die Hauptaufgaben des OR im weiten Sinne. ¹ Dabei ist die lineare Programmierung (LP) ² ein bedeutendes Teilgebiet des OR. Die betrachteten deterministischen Modelle werden durch den Simplex-Algorithmus, als wichtigstes Verfahren innerhalb der LP, gelöst. ³ Im Vordergrund der Modelle stehen allerdings kontinuierliche Entscheidungsvariablen innerhalb linearer Zielfunktionen. In der Realität hat man es aber oft mit Problemen zu tun, die teilweise (MIP ⁴ ) oder sogar ausschließlich (PIP) mit Hilfe ganzzahliger Entscheidungsvariablen modelliert werden müssen. Die Einplanung verschiedener unteilbarer Produktionsfaktoren ⁵ ist ein Beispiel dafür. Als Spezialfall der ganzzahligen Programmierung (IP) existiert die binäre ganzzahlige Programmierung (BIP). BIP-Modelle beruhen auf binären Entscheidungsvariablen, die man als Ja-Nein-Entscheidungen interpretieren kann. Bei der Lösung dieser Modelle ergeben sich allerdings Probleme bezüglich der Komplexität. Man benötigt deshalb Lösungsverfahren, die sich dieser Problematik annehmen und zu einer möglichst optimalen Lösung in vertretbarer Zeit führen. Ein mögliches Lösungsverfahren ist der Branch-and-Bound (B&B) Algorithmus, wobei sich zusätzlich verschiedene Techniken anwenden lassen.

Die vorliegende Arbeit richtet sich auf den Spezialfall der BIP-Probleme. Dazu werden verschiedene Aspekte des BIP in Kapitel eins betrachtet. Kapitel zwei fokussiert anschließend das Branch-and-Bound-Verfahren zur Lösung von BIP-Modellen. Die Arbeit schließt mit einer Bewertung der Thematik.

1 Vgl. [3], S. 1-2.

2 Beziehungsweise lineare Optimierung.

3 Vgl. [8], S. 482 und [3], S. 7.

4 In diesem Falle auch als MILP bezeichnet

5 Zum Beispiel Menschen und Maschinen.

2 2 BINARY INTEGER PROGRAMMING (BIP)

2 Binary Integer Programming (BIP)

Zu Beginn muss das Gebiet der ganzzahligen binären Programmierung unter verschiedenen Aspekten genauer betrachtet werden. Der erste Abschnitt zeigt mögliche BIP-Probleme in der Praxis. Dabei liegt der Fokus auf der Verdeutlichung der praktischen Relevanz von BIP-Problemen. Anschließend wird das allgemeine BIP-Optimierungsmodell ⁶ aufgestellt. Abschnitt drei zeigt Probleme bei der Berechnung von BIP-Modellen. In Abschnitt vier wird letztendlich ein Überblick über verschiedene Lösungsverfahren gegeben. Dabei erfolgt die Einordnung des Branch-and-Bound (B&B) Verfahrens zur Lösung von BIP-Problemen.

2.1 Probleme in der Praxis

Allgemein sind potentielle BIP-Probleme in der Praxis von Interesse. Abbildung 2.1 gibt zum Beispiel einen Überblick über Problemgruppen der kombinatorischen Optimierung, deren konkrete Probleme sich als BIP-Modell darstellen lassen.

Abbildung 2.1: Problemgruppen der kombinatorischen Optimierung (Quelle: [3], S. 121-122).

Allgemein geht es dabei um Entscheidungsprobleme, die sich auf Ja-Nein-Entscheidungen beziehen. Zur Verdeutlichung der Praxisrelevanz von BIP folgen nun weitere praktische Anwendungsbereiche. 7

6 Kurz „BIP-Modell“.

7 Auswahl der Anwendungen aus [6], S. 580-585.

3 2 BINARY INTEGER PROGRAMMING (BIP)

2.1.1 Planung fixer Investitionen

Die Planung von Investitionen bezieht sich oft auf Unternehmensentscheidungen über eine bestimmte Investitionshöhe. Daneben stehen Unternehmen aber auch vor dem Problem, ob in ein Projekt investiert werden soll oder nicht. ⁸ Als Entscheidungsprobleme von Unternehmen findet man zum Beispiel:

• Sollte man in eine Unternehmensfusion investieren?

• Sollte man in eine neue Produktionsstrecke investieren?

• Sollte man in eine bestimmte Sorte Rohmaterial für die Produktion investieren?

An diesen Fragestellungen lassen sich zum Beispiel unterschiedliche Unternehmensbereiche identifizieren, in denen Ja-Nein-Entscheidungsprobleme über Investitionen auftreten. Die allgemeine Frage im Bereich fixer Investitionen lautet dabei immer:

„Sollte eine bestimmte fixe Investition durchgeführt werden? “

Eine typische Anwendung ist die Maximierung des Kapitalwertes unter der Restriktion eines verfügbaren Investitionskapitals.

2.1.2 Standortauswahl

Im Rahmen der Globalisierung stehen Unternehmen auch vor der Entscheidung geeignete Standorte auszuwählen. ⁹ Als Ziele kann man zum Beispiel Kostensenkungen sowie die Erschließung neuer Märkte anführen. Die zentrale Frage bei der Standortauswahl ist immer:

„Sollte man einen bestimmten Standort für eine bestimmte Einrichtung wählen? “

Eine typische Anwendung ist die Minimierung der Standortkosten unter der Restriktion eines bestimmten gewünschten Produktionsoutputs. Standortprobleme treten unter anderem als Teilprobleme in anderen praktischen Anwendungen auf. 10

8 Investitionshöhe ist dabei fest vorgegeben.

9 Für zum Beispiel den Hauptsitz, Niederlassungen, Lagerhäuser, Produktionsstätten usw.

10 Zum Beispiel bei der Planung von Produktions- und Vertriebsnetzwerken (Vgl. [6]).

4 2 BINARY INTEGER PROGRAMMING (BIP)

2.1.3 Terminplanung für zusammenhängende Aktivitäten

Ein weiterer kritischer Punkt ist die zeitliche Einplanung verschiedener zusammenhängender Unternehmensaktivitäten. Unternehmen stehen zum Beispiel vor folgenden Entscheidungsproblemen:

• Wann sollte man Investitionen zur Unternehmensexpansion durchführen?

• Wann sollte die Produktion verschiedener Produkte beginnen?

• Wann sollten Marketingaktivitäten bezüglich neuer Produkte starten?

Die zentrale Frage der Terminplanung ist immer:

„Zu welcher Zeit sollte eine bestimmte Aktivität durchgeführt werden? “

Bei der Formulierung eines entsprechenden Entscheidungsmodells muss beachtet werden, dass für jede Aktivität eine Entscheidungsvariable pro Zeitspanne benötigt wird. ¹¹ Weiterhin kann eine Aktivität nur in einer bestimmten Zeitspanne beginnen. Aus diesem Grund steht man vor einer speziellen Auswahlsituation (MCS), in der die einzelnen Zeitspannen als verschiedene Alternativen für den Beginn einer Aktivität bereitstehen. Eine Aktivität wird dann in einer bestimmten Zeitspanne eingeplant und kann anschließend in keiner anderen Zeitspanne mehr eingeplant werden. ¹² Bei der Modellformulierung setzt man spezielle Gruppen von Variablen (SOS) ein. ¹³ Diese Vorgehensweise wird für alle einzuplanenden Aktivitäten durchgeführt. Das Ziel dabei kann zum Beispiel die Maximierung des Gewinns sein.

Darüberhinaus existieren noch viele weitere BIP-Probleme, weshalb die Notwendigkeit der speziellen Betrachtung dieser Probleme und Möglichkeiten zur Lösung gegeben ist.

11 Anzahl der Entscheidungsvariablen = Anzahl der Aktivitäten * Anzahl der Zeitspannen.

12 Starke MCS.

13 Vgl. [1], S. 7.

5 2 BINARY INTEGER PROGRAMMING (BIP)

2.2 Allgemeines Optimierungsmodell

Die Modellierung von BIP-Problemen richtet sich nach einem allgemeinen BIP-Modell, dessen konkrete Instanz für ein spezifisches BIP-Problem steht. Das BIP-Modell bezieht sich auf die Optimierung einer Zielfunktion Z = F (x) mit:

Z =

unter den Nebenbedingungen

a ij , c j , b i ∈ R für j = 1, ..., n ; i = 1, ..., m (2.3)

x j ∈ B für j = 1, ..., n (2.4)

Die verwendeten Symbole haben dabei folgende Bedeutung:

m ... Anzahl der Restriktionen

n ... Anzahl der Entscheidungsvariablen Z ... Zielfunktion x j ... binäre Entscheidungsvariablen c j ... Koeffizienten der Zielfunktion b i ... Kapazitätsgrenzen der Restriktionen a ij ... Koeffizienten der Matrix des Restriktionensystems

In 2.1 ist die Zielfunktion abgebildet, die maximiert oder minimiert werden soll. Hier werden in der Realität verschiedene Größen ¹⁴ betrachtet. Allgemein bezieht man sich bei der Maximierung auf einen Nutzen und bei der Minimierung auf Kosten. ¹⁵ In 2.2 ist das Restriktionensystem bestehend aus m Ungleichungen und/oder Gleichungen gegeben. Der Wertebereich der Koeffizienten (a ij , c j ) und Kapazitäten (b i ) wird durch 2.3 angegeben. Der zentrale Punkt von BIP-Modellen ist jedoch in 2.4 aufgeführt. Die n Entscheidungsvariablen des Optimierungsmodells können nur die Werte 0 und 1 annehmen. Es handelt sich somit um binäre Entscheidungsvariablen. Diese Einschränkung verdeutlicht, dass BIP-Modelle ein Spezialfall von IP-Modellen sind.

14 Zum Beispiel Maximierung des Deckungsbeitrages, Minimierung des Verschnitts usw.

15 Vgl. [3], S. 4.

6 2 BINARY INTEGER PROGRAMMING (BIP)

2.3 Berechnungsschwierigkeiten

Vor dem Hintergrund der effizienten Lösbarkeit von LP-Modellen ¹⁶ könnte man vermuten, dass BIP-Modelle durch ihre gewisse Beschränktheit noch effizienter lösbar ¹⁷ sind. Die Beschränktheit resultiert aus einer festen Eingabegröße ¹⁸ und der Verwendung von Binärvariablen. Man erhält dadurch eine endliche Anzahl potentieller Lösungen. Dennoch sind BIP-Probleme schwerer zu lösen als LP-Probleme. Zunächst kann die endliche Anzahl an möglichen Lösungen sehr groß werden.Für eine Eingabegröße von n Entscheidungsvariablen existieren 2 ⁿ potentielle Lösungen. Die potentielle Lösungsmenge wächst somit exponentiell mit steigender Eingabegröße und ist nicht polynomial beschränkt. ¹⁹ Tabelle 2.1 zeigt die Anzahl der möglichen Lösungen bezüglich unterschiedlicher Eingabegrößen n. Weiterhin sind BIP-Modelle

Tabelle 2.1: Lösungsmengen eines BIP-Modells für verschiedene Eingabegrößen (Quelle: Eigene Darstellung).

nicht leichter als LP-Modelle zu lösen, nur weil die nicht-ganzzahligen Lösungen durch die Binärbedingung aus dem Problem entfernt wurden. Vielmehr sorgt der Einbezug von kontinuierlichen Variablen dafür, dass LP-Modelle mit dem Simplex-Algorithmus effizienter zu lösen sind als BIP-Modelle. ²⁰ Allerdings existieren auch BIP-Modelle, für die der Simplex-Algorithmus eine zulässige Lösung ergibt. Dieser Umstand ergibt sich aus der speziellen Struktur dieser Modelle. Generell ist die Anwendung des Simplex-Algorithmus für BIP-Probleme jedoch nicht geeignet. Insgesamt entstehen Berechnungsschwierigkeiten maßgeblich aufgrund der folgenden zwei Faktoren: 21

• die Anzahl der binären Entscheidungsvariablen

• die spezifische Problemstruktur

16 Bis auf einige speziell konstruierte Modelle.

17 Effizienter lösbar bezieht sich hier allgemein auf die Komplexität der Lösung eines Modells.

18 Anzahl der Entscheidungsvariablen.

19 Jede Exponentialfunktion mit Basis echt größer 1 wächst schneller als jedes Polynom (Vgl. [2], S.

53).

20 Vgl. [6], S. 600-601.

21 Ebenda, S. 601.

7 2 BINARY INTEGER PROGRAMMING (BIP)

2.4 Lösungsalgorithmen im Überblick

Die konkrete Anwendung eines Algorithmus zur Lösung eines BIP-Problems ist mit einem bestimmten Aufwand ²² verbunden. Von zentraler Bedeutung ist dabei die benötigte Rechenzeit, die sich auf die Menge der elementaren Schritte des Algorithmus bezieht und durch die Modellstruktur sowie die Eingabegröße des zugrunde liegenden Problems bestimmt wird. ²³ In diesem Zusammenhang spricht man auch von der Komplexität eines Algorithmus. Zur Lösung von Problemen strebt man insgesamt die Verwendung von Algorithmen polynomialer Komplexität an. ²⁴ Nun steht man bei BIP-Problemen aber vor dem Problem der exponentiell mit der Eingabegröße wachsenden Anzahl potentieller Lösungen. Lösungsalgorithmen müssen sich diese Problematik berücksichtigen. Eine Klassifikation von Algorithmen zur Lösung von BIP-Problemen ist in Abbildung 2.2 dargestellt. 25

Abbildung 2.2: Klassifikation von Lösungsalgorithmen nach deren Lösungsgüte (Quelle: [3], S. 126-127).

Exakte Algorithmen sind durch eine hohe Rechenzeit gekennzeichnet, liefern aber in endlich vielen Schritten eine optimale Lösung des Problems. ²⁶ Heuristiken sind

22 Notwendiger Speicherplatz und benötigte Rechenzeit als Berechnungskomplexitäten (Vgl. [7], S.

175).

23 Vgl. [3], S. 125.

24 Thematisierung in [2].

25 Da BIP ein Spezialfall von IP ist, lassen sich die IP-Lösungsalgorithmen auch auf BIP-Probleme

anwenden.

26 Wenn nicht, dann ist das Problem unlösbar oder unbeschränkt.

8 2 BINARY INTEGER PROGRAMMING (BIP)

durch eine niedrige Rechenzeit gekennzeichnet, liefern allerdings nur eine zulässige Lösung des Problems. ²⁷ Zwischen exakten Algorithmen und Heuristiken stehen Approximationsalgorithmen. Sie ermitteln zwar nicht die beste Lösung eines Problems, aber man kann dafür garantieren, dass sie sich in der Nähe ²⁸ der optimalen Lösung befindet. ²⁹ Wünschenswert ist die Ermittlung der optimalen Lösung eines BIP-Problems, weshalb man sich den exakten Verfahren widmen muss. Als eine Variante von exakten Verfahren lassen sich Entscheidungsbaumverfahren nennen. Diese gliedern sich unter anderem in Verfahren der vollständigen und der begrenzten Enumeration. ³⁰ Bei der vollständigen Enumeration prüft ein Algorithmus jede mögliche Lösung auf Durchführbarkeit ³¹ und ermittelt für durchführbare Lösungen den entsprechenden Zielfunktionswert. ³² Der Algorithmus ist somit nicht mehr polynomial im Rechenaufwand. Für kleine BIP-Probleme mit zusätzlich wenigen Restriktionen ist diese Vorgehensweise vertretbar. Komplexe ³³ BIP-Probleme können allerdings nicht in vertretbarer Zeit gelöst werden, was aber das eigentliche Ziel ist. Abhilfe schaffen Verfahren der begrenzten Enumeration. Dabei unterbricht man die Berechnung einer neuen Lösung, wenn absehbar ist, dass der neue Zielfunktionswert schlechter als der Zielfunktionswert der besten bisher bekannten Lösung sein wird. ³⁴ Ein konkretes Verfahren im Rahmen der begrenzten Enumeration ist der Branch-and-Bound (B&B) Algorithmus, der für die weiteren Betrachtungen der Arbeit zur Lösung von BIP-Problemen relevant ist.

27 Vgl. [3], S. 126-127.

28 Güte der Lösung muss abgeschätzt werden.

29 Vgl. [10], S. 724.

30 Vgl. [3], S. 126.

31 Bezüglich der Restriktionen.

32 Vgl. [6], S. 600.

33 Komplex bezüglich deren Anzahl an Entscheidungsvariablen (siehe 2.3).

34 Vgl. [4], S. 12.

9 3 BRANCH-AND-BOUND (B&B) ZUR LÖSUNG VON BIP-PROBLEMEN

3 Branch-and-Bound (B&B) zur Lösung von

BIP-Problemen

Ausgangspunkt bei der Lösung von BIP-Problemen ist nun ein reales Problem in Form eines entsprechend 2.2 erstellten BIP-Optimierungsmodell. In diesem Kapitel wird nun der B&B-Algorithmus als Verfahren der begrenzten Enumeration zur Lösung solcher Modelle vorgestellt. Im ersten Abschnitt wird das Konzept des Algorithmus anhand der abstrakten Lösungsschritte erläutert. In Abschnitt zwei erfolgt anschließend die Lösung eines konkreten BIP-Problems, um die B&B-Arbeitsweise zu verdeutlichen. Als Beispiel wird dafür ein Rucksackproblem ³⁵ herangezogen. Abschnitt drei zeigt letztendlich verschiedene Ansatzpunkte für alternative Techniken innerhalb des B&B-Verfahrens.

3.1 Lösungsschritte

Das Ziel von B&B ist, dass man schnell zu der optimalen Lösung gelangt und dafür nur eine geringe Anzahl potentieller Lösungen durchsuchen muss. B&B richtet sich nach dem Prinzip „Teile-und-Herrsche“. Man steht zu Beginn vor einem oft großen und schwierigen Ausgangsproblem, das im Laufe des Verfahrens sukzessive in kleinere Teilprobleme zerlegt wird. Dieser Vorgang wird als „Branching“ ³⁶ bezeichnet. Für die entstehenden Teilprobleme werden anschließend Schranken berechnet. Diesen Vorgang bezeichnet man als „Bounding“ ³⁷ . Die ermittelten Schranken unterzieht man drei Tests, um ein Teilproblem gegebenenfalls sondieren zu können. Dieser Vorgang wird als „Fathoming“ ³⁸ oder besser als „Sondierung“ bezeichnet. Dadurch werden Teilmengen an möglichen Lösungen des BIP-Problems schrittweise entfernt, ohne alle Lösungen darin einzeln betrachtet zu haben. ³⁹ Nach jedem bearbeiteten Teilproblem erfolgt ein Optimalitätstest, durch den bestimmt wird, ob das Verfahren endet oder noch weitere unbearbeitete Teilprobleme existieren. Am Ende des Verfahrens erhält man als Ergebnis entweder die optimale Lösung des Problems oder es existiert keine Lösung. In den folgenden Abschnitten wird das iterative Verfahren abstrakt beschrieben. Neben der Initialisierung des Verfahrens bilden das Branching, das Bounding, die Sondierung und der Optimalitätstest eine vollständige Iteration. Betrachtet wird fortfolgend die Maximierung eines BIP-Problems. Bei der Lösung eines Minimierungsproblems ändert

35 Auch englisch als Knapsack-Problem oder seltener als Tornister-Problem bezeichnet.

36 Verzweigung oder auch Partitionierung.

37 Beschränkung oder auch Schrankenberechnung.

38 Fathoming (Vgl. [6], S. 607) wird in deutscher Literatur auch bezeichnet als Elimination (Vgl. [4],

S. 170), Auslotung (Vgl. [3], S. 133) oder Sondierung (Vgl. [5], S. 388).

39 Verkleinerung des Suchraumes.

10 3 BRANCH-AND-BOUND (B&B) ZUR LÖSUNG VON BIP-PROBLEMEN

sich maßgeblich die Verwendung der Schranken, wobei die Schritte inhaltlich aber gleich bleiben. ⁴⁰ Notwendige Abwandlungen werden an der entsprechenden Stelle angegeben.

3.1.1 Initialisierung (Iteration 0)

Im Rahmen der Initialisierung des Verfahrens wird zunächst eine Variable Z ^∗ L definiert

und mit −∞ initialisiert. Es handelt sich dabei um eine globale untere Schranke (Lower Bound ) für den Zielfunktionswert einer optimalen Lösung des BIP-Problems. ⁴¹ Sie nimmt im Laufe des Verfahrens immer die aktuell beste bekannte zulässige Lösung des Gesamtproblems entgegen. Sie wird auch als „amtierende Lösung“ bezeichnet. ⁴² Anschließend werden nacheinander die Schritte Bounding, Sondierung und Optimalitätstest für das Ausgangsproblem ausgeführt. Das Ausgangsproblem ist anschließend entweder sondiert oder muss als ein weiteres unbearbeitetes Teilproblem in einer vollen Iteration betrachtet werden. Zur Zwischenspeicherung von unbearbeiteten Problemen wird eine Warteschlange verwendet. 43

Bei der Minimierung eines BIP-Problems wird die Variable Z ^∗ U verwendet und mit

+∞ initialisiert. Man hat es in diesem Fall mit einer globalen oberen Schranke (Upper Bound ) für den Zielfunktionswert einer optimalen Lösung des BIP-Problems zu tun.

3.1.2 Branching

In diesem Schritt wird ein nicht bearbeitetes Teilproblem in zwei kleinere BIP-Teilprobleme partitioniert. Diese Verzweigung wird derart vorgenommen, dass zunächst irgendeine Entscheidungsvariable x j als Branching-Variable ⁴⁴ ausgewählt und im Anschluss einmal auf x j = 0 und einmal auf x j = 1 fixiert wird. Abbildung 3.1 zeigt diese Verzweigung eines Teilproblems. Die entstehenden Teilprobleme gelten als unbearbeitet. Das in beide Richtungen verzweigte Teilproblem kann als bearbeitet markiert werden. ⁴⁵ Durch das Branching entsteht somit im Laufe des Lösungsprozesses ein binärer Baum mit spezifischen Eigenschaften ⁴⁶ , der auch als Lösungsbaum bezeichnet wird. ⁴⁷ Die Wurzel des Baumes stellt das BIP-Ausgangsproblem dar. Die

40 Vgl. [5], S. 389.

41 Vgl. [3], S. 132.

42 Vgl. [5], S. 388.

43 Vgl. [6], S. 608.

44 Oder auch Verzweigungs-Variable.

45 Bei der Verzweigung eines Teilproblems in nur eine Richtung bleibt es weiter unbearbeitet.

46 Vgl. [9], S. 180 ff. und speziell [2], S. 1091 ff.

47 Vgl. [6], S. 608.

Abbildung 3.1: Verzweigung eines BIP-Teilproblems in zwei neue BIP-Teilprobleme (Quelle: Eigene Darstellung).

Blätter auf der untersten Ebene des gesamten Lösungsbaumes verkörpern die möglichen Lösungen des BIP-Problems. An dieser Stelle kann nicht weiter verzweigt werden.

3.1.3 Bounding

In diesem Schritt erfolgt die Schrankenberechnung für ein Teilproblem. Das Teilproblem wird dazu relaxiert und anschließend gelöst. Eine geeignete Möglichkeit ist zum Beispiel die LP-Relaxation ⁴⁸ . Aus dem Teilproblem wird dabei die Binärbedingung entfernt und die Entscheidungsvariablen auf das Intervall [0, 1] erweitert. Die entstehende LP-Relaxation lässt sich nun effizient durch Anwendung des Simplex-Algorithmus lösen. Der sich ergebende Zielfunktionswert stellt die lokale obere Schranke ⁴⁹ Z U (Upper Bound ) des BIP-Teilproblems dar.

Bezüglich der Minimierung nimmt die lokale untere Schranke Z L (Lower Bound ) den Zielfunktionswert der LP-Relaxation entgegen.

3.1.4 Sondierung

In diesem Schritt wird die ermittelte obere Schranke eines Teilproblems drei Schrankentests unterzogen. Sollte ein Test erfüllt sein, so wird das entsprechende Teilproblem ⁵⁰ von der weiteren Betrachtung ausgeschlossen und gilt als sondiert. Dadurch begrenzt man die zu untersuchende Menge der möglichen Lösungen. Folgende Tests werden durchgeführt:

Test 1 Z U des Teilproblems ≤ Z ∗

L

Test 2 Lösung ist zulässig für das Ausgangsproblem AND Z U > Z ∗

L

Test 3 Es existiert keine Lösung des Teilproblems

48 Auch als LP-Auflockerung bezeichnet (Vgl. [5]).

49 Vgl. [3], S. 132.

50 Und damit auch alle darunter liegenden Teilprobleme.

12 3 BRANCH-AND-BOUND (B&B) ZUR LÖSUNG VON BIP-PROBLEMEN

Ist der erste Test erfüllt, so ist die obere Schranke eines Teilproblems schlechter als die bisher amtierende Lösung des Gesamtproblems. Greift der zweite Test, so ist die Lösung zulässig für das Ausgangsproblem. Weiterhin ist die obere Schranke des Teilproblems auch noch größer als die amtierende Lösung, weshalb diese durch die Lösung des Teilproblems mittels Z ^∗ L = Z U ersetzt wird. Zusätzlich wird der Sondierungstest eins

für alle Teilprobleme in der Warteschlange wiederholt. Ist der dritte Test erfüllt, dann existiert keine Lösung des Teilproblems. Kann ein Teilproblem nicht sondiert werden, dann wird es in die Warteschlange eingefügt.

Im Rahmen eines Minimierungsproblems ändern sich die Tests wie folgt:

Test 1 Z L des Teilproblems ≥ Z ∗

U

Test 2 Lösung ist zulässig für das Ausgangsproblem AND Z L < Z ∗

U

Test 3 Es existiert keine Lösung des Teilproblems

Wenn in diesem Fall der Test zwei greift, dann erfolgt der Schritt Z ^∗ U = Z L .

3.1.5 Optimalitätstest

Das B&B-Verfahren endet, wenn sich keine Teilprobleme mehr in der Warteschlange befinden und man erhält Z ^∗ L (bzw. Z ^∗ U bei der Minimierung) als Ergebnis. Ansonsten folgt eine weitere Iteration. 51

3.2 Lösung eines Rucksackproblems

Zur Demonstration des B&B-Verfahrens wird in diesem Abschnitt nun ein Rucksackproblem herangezogen. Dabei kann man sich folgende Situation vereinfacht vorstellen. Ein Wanderer hat einen Rucksack und steht vor der Aufgabe verschiedene Gegenstände einzupacken. Jeder Gegenstand hat dabei einen bestimmten Nutzen für den Wanderer, aber gleichzeitig ein bestimmtes Gewicht. Er muss nun für jeden Gegenstand entscheiden, ob er ihn einpackt oder nicht. Es handelt sich somit um ein BIP-Problem. Der Wanderer kann dabei unterschiedliche Zielsetzungen verfolgen. Die erste mögliche Variante ist die Minimierung des Gewichts unter der Einhaltung eines Minimalnutzens. Eine weitere Variante ist die Maximierung des Nutzens unter Einhaltung einer bestimmten Gewichtskapazität. Ein solches BIP-Maximierungsproblem wird nun an einem Beispiel mit dem B&B-Verfahren gelöst.

51 Vgl. [6], S. 609.

13 3 BRANCH-AND-BOUND (B&B) ZUR LÖSUNG VON BIP-PROBLEMEN

Zur Vereinfachung wird weiterhin von einem mehrfach restringierten Rucksackproblem abgesehen. Zunächst existieren drei Gegenstände mit den Daten aus Tabelle 3.1, die man in den Rucksack packen kann. Weiterhin ist eine Gewichtsbegrenzung von 10 Gewichtseinheiten gegeben.

Tabelle 3.1: Beispielwerte für ein Rucksackproblem (Quelle: Eigene Darstellung).

Das zu den Beispielwerten gehörende BIP-Modell lässt sich aus 2.2 ableiten und sieht wie folgt aus:

Z = 9 · x 1 + 5 · x 2 + 2 · x 3 → MAX! (3.1)

unter der Nebenbedingung

6 · x 1 + 3 · x 2 + 5 · x 3 ≤ 10 (3.2)

x 1 , x 2 , x 3 ∈ B (3.3)

Das B&B-Verfahren startet mit der Iteration 0. Zunächst wird die Variable Z ^∗ L mit

−∞ initialisiert. Anschließend folgt der Bounding-Schritt für das Ausgangsproblem. Relaxiert wird das Problem dabei durch Entfernung der Binärbedingung und Angabe des Intervalls [0, 1] für die einzelnen Entscheidungsvariablen. Das Problem lässt sich nun mit dem Simplex-Algorithmus lösen, woraus sich die obere Schranke Z U = 14.4 ergibt. Das Bounding ist damit abgeschlossen, so dass man die berechnete obere Schranke den Sondierungstests unterziehen kann. Dabei ist folgendes festzustellen:

Test 1 14.4 ≤ −∞ → nicht erfüllt

Test 2 (1, 1, 0.2) ist zulässig AND 14.4 > −∞ → nicht erfüllt

Test 3 Es existiert keine Lösung → nicht erfüllt

Es trifft kein Fall zu, wodurch das Ausgangsproblem nicht sondiert werden kann. Der entstehende Lösungsbaum ist in Abbildung 3.2 dargestellt, wobei „Root“ das Ausgangsproblem bezeichnet. Die rote Markierung verdeutlicht, dass das Problem noch nicht bearbeitet wurde und dadurch als Teilproblem 0 (TP 0 ) in einer Warteschlange abgelegt wird. Die erste Iteration startet also mit TP 0 .

Abbildung 3.2: Rucksackproblem - Iteration 0 (Quelle: Eigene Darstellung).

Iteration 1:

Der erste Schritt der Iteration ist der Branching-Schritt. TP 0 wird durch die Fixierung der ersten Entscheidungsvariablen x 1 auf x 1 = 1 (TP 1 ) und x 1 = 0 (TP 2 ) verzweigt. ⁵² Für die zwei neuen Teilprobleme wird jeweils der Bounding Schritt durchgeführt. Dies erfolgt wieder durch die Lösung der beiden LP-Relaxationen. Als Ergebnis erhält man:

TP 1 (x 1 = 1) : Z U = 14.4; (1, 1, 0.2)

TP 2 (x 1 = 0) : Z U = 7; (0, 1, 1)

Beide Teilprobleme können nun auf Sondierung geprüft werden. Für TP 1 ist keiner der Schrankentests erfüllt, so dass es unbearbeitet in der Warteschlange abgelegt wird. TP ² kann sondiert werden, da der zweite Sondierungstest dafür erfüllt ist:

Test 2 (0, 1, 1) ist zulässig AND 7 > −∞ → erfüllt

Die Lösung der LP-Relaxation ist für das Ausgangsproblem zulässig und auch die obere Schranke ist größer als die amtierende Lösung, woraus sich folgende Änderung ergibt:

Änderung: 7 > −∞ → Z ^∗ L = 7

Anschließend folgt sofort die Wiederholung des Schrankentest eins für alle Teilprobleme in der Warteschlange. Es handelt sich dabei um TP 1 , das aber auch jetzt nicht sondiert werden kann. Die Veränderungen am Lösungsbaum nach dieser ersten Iteration sind in Abbildung 3.3 dargestellt, wobei sondierte Teilprobleme fortfolgend Grün und noch unbearbeitete Teilprobleme Rot markiert werden. Mit dem Ende dieser Iteration befindet sich TP 1 noch in der Warteschlange und wird somit für die nächste Iteration herangezogen. Das Ausgangsproblem „Root“ gilt als bearbeitet, aber noch nicht ausgelotet.

52 Auswahl der Branching-Variable erfolgt hier nach der natürlichen Reihenfolge der

Entscheidungsvariablen.

Abbildung 3.3: Rucksackproblem - Iteration 1 (Quelle: Eigene Darstellung).

Iteration 2:

Man beginnt wieder mit dem Branching von TP 1 . An dieser Stelle wird als nächste Entscheidungsvariable x 2 auf x 2 = 1 (TP 3 ) und x 2 = 0 (TP 4 ) fixiert. Die anschließende Durchführung des Bounding-Schrittes ergibt folgende Lösungen:

TP 3 (x 2 = 1) : Z U = 14.4; (1, 1, 0.2)

TP 4 (x 2 = 0) : Z U = 10.6; (1, 0, 0.8)

Die Durchführung der Sondierungstests ergibt, dass man keines der beiden Teilprobleme eliminieren kann. Sie gelten beide als unbearbeitete Teilprobleme und werden in der Warteschlange abgelegt.

Abbildung 3.4: Rucksackproblem - Iteration 2 (Quelle: Eigene Darstellung).

Der neue Lösungsbaum nach Iteration 2 ist in Abbildung 3.4 dargestellt.

Iteration 3:

Es wird nun eines der verbleibenden offenen Teilprobleme aus der Warteschlange ausgewählt und bearbeitet. Dabei kann man in der natürlichen Reihenfolge der Probleme vorgehen. Somit wird in dieser Iteration das offene TP 3 ausgewählt

16 3 BRANCH-AND-BOUND (B&B) ZUR LÖSUNG VON BIP-PROBLEMEN

und bearbeitet. Im Rahmen des Branching-Schrittes bleibt jetzt nur noch die Entscheidungsvariable x 3 zur Fixierung auf x 3 = 1 (TP 5 ) und x 3 = 0 (TP 6 ) übrig. Der Bounding-Schritt ergibt folgendes für die jeweiligen LP-Relaxationen:

TP 5 (x 3 = 1) : keine Lösung für (1, 1, 1)

TP 6 (x 3 = 0) : Z U = 14; (1, 1, 0)

Die Anwendung der Sondierungstests für das TP 5 ergibt, dass es ausgelotet ist:

Test 3 es existiert keine Lösung → erfüllt

Das TP 6 kann sondiert werden, da der Sondierungstest zwei greift:

Test 2 (1, 1, 0) ist zulässig AND 14 > 7 → erfüllt

Die amtierende Lösung muss entsprechend geändert werden:

Änderung: 14 > 7 → Z ^∗ L = 14

Im Anschluss führt man den Sondierungstest eins erneut auf alle Teilprobleme der Warteschlange aus. Fokussiert wird das TP 4 , für das der Test nun erfüllt ist. Es kann damit auch aus der Warteschlange entfernt werden. Nach diesem Schritt ist auch der Optimalitätstest erfüllt, da sich jetzt keine Teilprobleme mehr in der Warteschlange befinden. Das gesamte BIP-Problem ist damit gelöst und hat die amtierende Lösung als Ergebnis:

Ergebnis: Z ^∗ L = 14 mit x 1 = 1, x 2 = 1, x 3 = 0

Der gesamte Lösungsbaum ist in Abbildung 3.5 dargestellt.

Abbildung 3.5: Rucksackproblem - vollständiger Lösungsbaum (Quelle: Eigene Darstellung).

Das Rucksacksackproblem konnte in 3 Iterationen gelöst werden. Der Wanderer nimmt in diesem Fall die ersten beiden Gegenstände mit und maximiert mit 14 Nutzeneinheiten dadurch seinen Gesamtnutzen.

17 3 BRANCH-AND-BOUND (B&B) ZUR LÖSUNG VON BIP-PROBLEMEN

3.3 Alternative Techniken

Das B&B-Verfahren ist in seiner Grundstruktur durch die Arbeitsschritte Initialisierung, Branching, Bounding, Sondierung sowie Optimalitätstest abstrakt vorgeschrieben. Innerhalb der ersten drei Schritte können allerdings verschiedene Techniken zum Einsatz kommen. Das übergeordnete Ziel ist dabei, dass die Berechnung der optimalen Lösung eines BIP-Problems in einer möglichst geringen Anzahl von Iterationen und zusätzlich effizient erfolgt. In diesem Abschnitt wird nun ein Überblick über einige Techniken innerhalb der einzelnen B&B-Arbeitsschritte gegeben.

3.3.1 Modellierungstechnik

Vor der konkreten Betrachtung der einzelnen Arbeitsschritte ist zunächst anzumerken, dass die Form eines BIP-Modells die B&B-Berechnung beeinflusst. Deutlich wird das zum Beispiel beim Rucksackproblem mit einer Restriktion. Nimmt man das Beispiel aus 3.2 (Maximierung des Gesamtnutzens bei Einhaltung einer Gewichtskapazität), so ist es besser das BIP-Modell alternativ zu gestalten. Die Anordnung der einzelnen Gegenstände ⁵³ nach ihren absteigenden Nutzen pro Gewichtseinheit wäre von Vorteil, wodurch die Initialisierung des B&B-Verfahrens optimiert werden kann. 54

3.3.2 Techniken der Initialisierung (Iteration 0)

In der Iteration 0 steht bei der Maximierung/Minimierung die Initialisierung einer globalen unteren/oberen Schranke im Vordergrund, wobei zum Beispiel folgende Techniken Anwendung finden:

Variante 1 Anwendung einer Heuristik

Variante 2 Belegung mit −∞ (Maximierung) / +∞ (Minimierung)

Variante 3 Ableitung aus der gelösten LP-Relaxation des Ausgangsproblems

Die globale Schranke kann zunächst durch Anwendung einer Heuristik bestimmt werden. ⁵⁵ Eine Alternative ist die Fixierung der Schranke auf −∞/ + ∞. Durch eine solche unscharfe Angabe arbeitet das B&B-Verfahren jedoch nicht besser. Die dritte Variante beeinflusst den Ablauf des B&B-Verfahrens maßgeblich. Man löst dazu die LP-Relaxation des Ausgangsproblems und leitet aus dem Ergebnis eine globale

53 Und damit auch der einzelnen Entscheidungsvariablen.

54 Vgl. [3], S. 138.

55 Ebenda, S. 134.

18 3 BRANCH-AND-BOUND (B&B) ZUR LÖSUNG VON BIP-PROBLEMEN

untere/obere Schranke ab. Dabei hilft eine geeignete Modellierung des BIP-Problems. Man modelliert zum Beispiel das Rucksackproblem als Maximierungsproblem mit einer Restriktion nach 3.3.1. Anschließend wird die LP-Relaxation dieses Ausgangsproblems gelöst. Durch Anordnung der Entscheidungsvariablen nach absteigendem Nutzen pro Gewichtseinheit werden so lange Gegenstände mitgenommen, bis die Gewichtskapazität überschritten ist. Unter Umständen wird ein Gegenstand dabei nur anteilig mitgenommen. ⁵⁶ Diesen Gegenstand schaltet man entsprechend der Binärbedingung auf den Wert 0. Die entstehende Lösung ist zulässig für das Ausgangsproblem und der zugehörige Zielfunktionswert kann zur Initialisierung der globalen unteren Schranke verwendet werden. 57

Schafft man es also die obere/untere Schranke bei der Maximierung/Minimierung geeignet zu initialisieren, dann wird der Ablauf von B&B effizienter. Teilprobleme können eher sondiert werden oder wurden von vornherein ausgeschlossen.

3.3.3 Branching-Techniken

Im Branching-Schritt geht es zu Beginn um die Frage, welches Teilproblem (TP) zur Verzweigung ausgewählt werden soll. Man kann sich dazu vorstellen, dass die unbearbeiteten TP in einer Warteschlange liegen. Die Varianten zur Auswahl können nun sein:

Variante 1 LIFO-Regel

A. Reine Tiefensuche

B. Tiefensuche mit vollständiger Verzweigung

Variante 2 MUB-Regel (Maximierung) / MLB-Regel (Minimierung)

Man kann zum Beispiel die LIFO-Regel (Last In - First Out) zur Auswahl eines TP aus der Warteschlange anwenden, wobei das zuletzt eingefügte TP zur Verzweigung ausgewählt wird. ⁵⁸ Bei der reinen Tiefensuche als Spezialfall wird danach das ausgewählte TP nur einseitig in ein neues TP verzweigt, wodurch es danach nicht als bearbeitet markiert werden kann. Das neue TP wird anschließend dem Bounding und den Sondierungstests unterzogen. Konnte das TP nicht sondiert werden, so wird es zunächst in der Warteschlange abgelegt und in der folgenden Iteration nach der LIFO-Regel als zu verzweigendes TP ausgewählt. Ansonsten erfolgt die Verzweigung

56 Wenn nicht wäre die Lösung der LP-Relaxation des Ausgangsproblems zulässig und das Problem

wäre gelöst.

57 Vgl. [3], S. 138-139.

58 Ebenda, S. 136-137.

19 3 BRANCH-AND-BOUND (B&B) ZUR LÖSUNG VON BIP-PROBLEMEN

des vorigen TP in die andere Richtung. Die LIFO-Regel und der Spezialfall der Tiefensuche mit vollständiger Verzweigung wurde in 3.2 verwendet. Das ausgewählte TP wird dabei gleich in zwei neue TP verzweigt, wodurch es anschließend als bearbeitet markiert werden kann. ⁵⁹ Eines der beiden neuen TP wird dann für den Bounding-Schritt herangezogen. Das andere TP wird in der Warteschlange abgelegt. Bei Verwendung der MUB-Regel (Maximum Upper Bound ) / MLB-Regel (Minimum Lower Bound ) wählt man zur Verzweigung das unbearbeitete TP mit der größten oberen/unteren Schranke aus. Insgesamt geht man bei der LIFO-Regel sofort in die Tiefe des Lösungsbaumes (Depth First Search) und erhält auch relativ schnell zulässige Lösungen für das Ausgangsproblem, die jedoch oft schlecht sind. ⁶⁰ Die Anwendung dieser Regel ist allerdings sehr effizient, da man auf dem Weg nach unten immer die vorhergehende Lösung einer LP-Relaxation verwenden kann und diese nur minimal reoptimieren muss. ⁶¹ Die MUB-/MLB-Regel ist nicht so effizient, da man mehr in die Breite des Lösungsbaumes geht (Breadth First Search). Dafür ist die erste ermittelte zulässige Lösung meist sehr gut. 62

Nach der Auswahl eines unbearbeiteten Teilproblems bleibt noch zu klären, welche Branching-Variable zur Verzweigung gewählt werden soll. Denkbar sind zum Beispiel folgende Varianten:

Variante 1 Auswahl nach der natürlichen Reihenfolge

Variante 2 Entscheidungsvariable mit dem größten nicht-ganzzahligen Anteil

Variante 3 Entscheidungsvariable mit dem kleinsten nicht-ganzzahligen Anteil

Die erste Variante wurde in 3.2 verwendet. Dadurch ist der weitere Verlauf des B&B-Verfahrens durch das zugrundeliegende BIP-Modell bestimmt, weshalb eine geeignete Modellierung erforderlich ist. In den anderen beiden Varianten wählt man die Entscheidungsvariable als Branching-Variable, die den größten/kleinsten ganzzahligen Anteil aufweist. ⁶³ Auch an dieser Stelle hängt der Erfolg vom zugrundeliegenden Problem ab.

59 Vgl. [3], S. 137.

60 Ebenda, S. 137.

61 Vgl. [6], S. 609.

62 Vgl. [3], S. 137.

63 Ebenda, S. 137.

20 3 BRANCH-AND-BOUND (B&B) ZUR LÖSUNG VON BIP-PROBLEMEN

3.3.4 Bounding-Techniken

An dieser Stelle steht die zu verwendende Relaxation im Vordergrund, durch die sich eine möglichst gute lokale obere/untere Schranke für ein betrachtetes Teilproblem ergibt. Folgende Relaxationen können unter anderem verwendet werden:

Variante 1 LP-Relaxation

Variante 2 Lagrange-Relaxation

Variante 3 Eliminierung von Restriktionen

Die erste Variante wurde in 3.2 verwendet. Man entfernt einfach die Binärbedingung und beschränkt die Entscheidungsvariablen auf das Intervall [0, 1]. Die LP-Relaxation kann anschließend in vielen Fällen effizient mittels Simplex-Algorithmus gelöst werden. Bei der Lagrange-Relaxation wird das Restriktionensystem entfernt und durch einen geeignet zu bestimmenden Lagrange-Multiplikator gewichtet in die Zielfunktion aufgenommen. ⁶⁴ Durch das Fehlen von Restriktionen, kann diese Relaxation sehr schnell gelöst werden, wobei aber anschließende Probleme bezüglich Sondierungstests auftreten. ⁶⁵ Eine dritte Variante besteht darin, dass man spezielle Restriktionen aus dem Ausgangsproblem entfernt. Dafür wählt man die Restriktionen aus, durch die das Problem extrem schwer lösbar wird. 66

3.4 Das Softwarewerkzeug „LPSolve“

Zur Lösung von BIP-Problemen mittels B&B ist der Einsatz entsprechender Software notwendig, die möglichst auch die verschiedenen Techniken implementiert. Ein Praxisbeispiel dafür ist das Softwarewerkzeug „LPSolve“, das momentan in der Version 5.5.0.13 frei verfügbar (LGPL ⁶⁷ ) vorliegt. ⁶⁸ Zusätzlich wird eine IDE mit einem entsprechenden GUI als „LPSolve IDE“ bereitgestellt. LPSolve ist ein MILP Solver, der den Simplex-Algorithmus für LP-Probleme und B&B für IP-Probleme anwendet. Weiterhin werden Bibliotheken für verschiedene Programmiersprachen ⁶⁹ zur Integration von LPSolve bereitgestellt. Der direkte Aufruf aus anderen Programmen ⁷⁰ wird durch die Verwendung spezifischer Treiber ermöglicht. Als Eingabeformate

64 Vgl. [3], S. 135 und [6], S. 613.

65 Vgl. [6], S. 613.

66 Zum Beispiel die Zyklusbedingung beim Traveling-Salesman-Problem (Vgl. [3], S. 136).

67 GNU Lesser General Public License.

68 Siehe http://sourceforge.net/projects/lpsolve.

69 Zum Beispiel C, Visual Basic, .NET, Delphi, Java.

70 Zum Beispiel AMPL, Matlab.

21 3 BRANCH-AND-BOUND (B&B) ZUR LÖSUNG VON BIP-PROBLEMEN

unterstützt LPSolve unter anderem das „LP-Format“ sowie das „MPS-Format“. BIP-Probleme lassen sich somit geeignet darstellen und mittels B&B lösen. Als Relaxation im Bounding-Schritt löst LPSolve die LP-Relaxation mittels Simplex Algorithmus. Ansonsten lassen sich verschiedene B&B- und Simplex-Techniken auswählen, um die Lösung des BIP-Problems gegebenenfalls zu optimieren. Neben dem ausführlichen Lösungsweg dokumentiert LPSolve zusätzlich die Anzahl der benötigten Iterationen sowie die Rechenzeit, was einen Vergleich verschiedener Techniken ermöglicht.

Die Modellierung des Rucksackproblems aus 3.2 in LPSolve ist in Abbildung 3.6 dargestellt. Der Lösungsprozess wird durch die spezifischen Einstellungen in LPSolve beeinflusst.

Abbildung 3.6: Rucksackproblem in LPSolve (Quelle: Eigene Darstellung).

22 4 BEWERTUNG

4 Bewertung

B&B als Verfahren der begrenzten Enumeration begegnet den Schwierigkeiten bei der Lösung von BIP-Problemen. Zum einen wird die enorme Lösungsmenge eines BIP-Problems sukzessive in kleinere und leichtere Teilprobleme partitioniert. Zum anderen relaxiert man diese Teilprobleme, um sie effizient zum Beispiel mit dem Simplex-Algorithmus lösen zu können. B&B ist damit effizienter als die vollständige Enumeration, bei der alle 2 ⁿ Blätter des Lösungsbaumes bearbeitet werden. Diese Erkenntnis wird beim Vergleich der Komplexitäten beider Verfahren deutlich. Man unterscheidet dabei den Rechenaufwand im besten, im mittleren und im schlechtesten Fall. ⁷¹ Bei der vollständigen Enumeration handelt es sich um ein Verfahren mit generell exponentiellem Rechenaufwand bei BIP-Problemen. Das B&B-Verfahren hat dagegen nur im schlechtesten Fall einen exponentiellen Rechenaufwand. ⁷² Für den besten und mittleren Fall kann man allgemein keine Angaben machen. Der Grund dafür liegt in der Variabilität des Verfahrens. B&B kann primär als abstrakte Vorgehensweise zur Lösung von BIP-Problemen gesehen werden. Erst durch den Einsatz verschiedener Techniken formt sich ein konkreter Algorithmus. Dafür lässt sich anschließend der Rechenaufwand ermitteln. Neben den speziellen Techniken innerhalb von B&B kommt der Modellierung eines BIP-Problems besondere Bedeutung zu. Durch sie wird der Ablauf von B&B maßgeblich bestimmt. Modelliert man ein BIP-Problem geeignet, so lässt sich die Anzahl der Iterationen verkleinern. Dies wirkt sich wiederum positiv auf den Rechenaufwand aus. Die Modellierung an sich hängt vom zugrunde liegenden BIP-Problem ab. Während sich das Rucksackproblem mit einem Umfang von bis zu 100.000 Entscheidungsvariablen mit relativ geringem Rechenaufwand lösen lässt, so ist man beim quadratischen Zuordnungsproblem auf deutlich weniger Entscheidungsvariablen beschränkt. ⁷³ Insgesamt kann man festhalten, dass das grundlegende BIP-Problem, dessen BIP-Modell sowie die eingesetzten Techniken das B&B-Verfahren beeinflussen. Ansonsten ist B&B unter Einsatz der verschiedenen Techniken im Normalfall durchaus geeignet, um BIP-Probleme effizient zu lösen.

71 Vgl. [2].

72 Vgl. [11], S. 9-10.

73 Vgl. [3], S. 126.

23 Literaturverzeichnis

Literaturverzeichnis

[1] Appa, Gautam ; Pitsoulis, Leonidas ; Williams, Hilary P.: Handbook on modelling for discrete optimization. New York : Springer, 2006

[2] Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald ; Stein, Clifford: Algorithmen - Eine Einführung. München : Oldenbourg Verlag, 2004

[3] Domschke, Wolfgang ; Drexl, Andreas: Einführung in Operations Research. 6. Auflage. Springer Verlag, 2005

[4] Ellinger, Theodor ; Beuermann, Günter ; Leisten, Rainer: Operations Research - Eine Einführung. 6. Auflage. Springer Verlag, 2003

[5] Hillier, Frederick S. ; Lieberman, Gerald J.: Operations Research - Einführung. 4. Auflage. München : Oldenbourg Verlag, 1988

[6] Hillier, Frederick S. ; Lieberman, Gerald J.: Introduction to operations research. 7th. edition. New York : McGraw-Hill, Inc., 2001

[7] Hromkovic, Juraj: Algorithmische Konzepte der Informatik - Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kryptographie. Wiesbaden (u.a.) : Teubner, 2001

[8] Lassmann, Wolfgang ; Picht, Jochen ; Rogge, Rolf: Wirtschaftsinformatik Kalender 2002. IM Marketing-Forum GmbH, 2001

[9] Schwarze, Jochen: Mathematik für Wirtschaftswissenschaftler. Bd. 3: Lineare Algebra, Lineare Optimierung und Graphentheorie. 11. Auflage. Herne/Berlin : Verlag Neue Wirtschafts-Briefe, 2000

[10] Sedgewick, Robert: Algorithmen in C. Bonn (u.a.) : Addison-Wesley, 1992

[11] Suhl, Leena ; Mellouli, Taieb: Optimierungssysteme - Modelle, Verfahren, Software, Anwendungen. Berlin (u.a.) : Springer, 2006