Branch-and-Bound-Techniken zur Lösung von BIP-Problemen

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

Abkürzungsverzeichnis

1 Abgrenzung der Themenstellung

2 Binary Integer Programming (BIP)
2.1 Probleme in der Praxis
2.1.1 Planung fixer Investitionen
2.1.2 Standortauswahl
2.1.3 Terminplanung für zusammenhängende Aktivitäten
2.2 Allgemeines Optimierungsmodell
2.3 Berechnungsschwierigkeiten
2.4 Lösungsalgorithmen im Überblick

3 Branch-and-Bound (B&B) zur Lösung von BIP-Problemen
3.1 Lösungsschritte
3.1.1 Initialisierung (Iteration 0)
3.1.2 Branching
3.1.3 Bounding
3.1.4 Sondierung
3.1.5 Optimalitätstest
3.2 Lösung eines Rucksackproblems
3.3 Alternative Techniken
3.3.1 Modellierungstechnik
3.3.2 Techniken der Initialisierung (Iteration 0)
3.3.3 Branching-Techniken
3.3.4 Bounding-Techniken
3.4 Das Softwarewerkzeug „LPSolve“

4 Bewertung

Literaturverzeichnis

Abbildungsverzeichnis

2.1 Problemgruppen der kombinatorischen Optimierung

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

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

3.2 Rucksackproblem - Iteration 0

3.3 Rucksackproblem - Iteration 1

3.4 Rucksackproblem - Iteration 2

3.5 Rucksackproblem - vollständiger Lösungsbaum

3.6 Rucksackproblem in LPSolve

Tabellenverzeichnis

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

3.1 Beispielwerte für ein Rucksackproblem

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

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.

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 in dieser Leseprobe nicht enthalten

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.⁷

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 dur chgefü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 Stan dort 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.¹⁰

[...]

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

² Beziehungsweise lineare Optimierung.

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

⁴ In diesem Falle auch als MILP bezeichnet

⁵ Zum Beispiel Menschen und Maschinen.

⁶ Kurz „BIP-Modell“.

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

⁸ Investitionshöhe ist dabei fest vorgegeben.

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

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