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.
[...]
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.1 Dabei ist die lineare Programmierung (LP)2 ein bedeutendes Teilgebiet des OR. Die betrachteten deterministischen Modelle werden durch den Simplex-Algorithmus, als wichtigstes Verfahren innerhalb der LP, gelöst.3 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 (MIP4) oder sogar ausschließlich (PIP) mit Hilfe ganzzahliger Entscheidungsvariablen modelliert werden müssen. Die Einplanung verschiedener unteilbarer Produktionsfaktoren5 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-Optimierungsmodell6 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.7
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.8 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.9 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.10
[...]
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.
6 Kurz „BIP-Modell“.
7 Auswahl der Anwendungen aus [6], S. 580-585.
8 Investitionshöhe ist dabei fest vorgegeben.
9 Für zum Beispiel den Hauptsitz, Niederlassungen, Lagerhäuser, Produktionsstätten usw.
Häufig gestellte Fragen
Was ist das Thema dieses Dokuments?
Dieses Dokument befasst sich mit Binary Integer Programming (BIP), insbesondere der Anwendung des Branch-and-Bound (B&B) Algorithmus zur Lösung von BIP-Problemen.
Was ist Binary Integer Programming (BIP)?
BIP ist ein Spezialfall der ganzzahligen Programmierung (IP), bei dem Entscheidungsvariablen nur die Werte 0 oder 1 annehmen können. Diese binären Variablen werden oft als Ja-Nein-Entscheidungen interpretiert.
Welche praktischen Probleme können mit BIP gelöst werden?
BIP-Modelle können in verschiedenen Bereichen eingesetzt werden, darunter die Planung fixer Investitionen (z.B. Investition in eine Fusion, neue Produktionsstrecke), Standortauswahl (z.B. Wahl eines Standorts für eine Einrichtung) und Terminplanung für zusammenhängende Aktivitäten.
Was ist der Branch-and-Bound (B&B) Algorithmus?
Der Branch-and-Bound Algorithmus ist ein Lösungsverfahren für BIP-Probleme. Er beinhaltet Schritte wie Initialisierung, Branching (Verzweigung), Bounding (Bestimmung von Schranken), Sondierung und Optimalitätstest, um eine optimale oder nahezu optimale Lösung zu finden.
Was sind die Herausforderungen bei der Lösung von BIP-Problemen?
BIP-Probleme können aufgrund ihrer Komplexität rechenintensiv sein. Daher werden effiziente Lösungsverfahren benötigt, die in angemessener Zeit zu einer Lösung führen.
Welche alternativen Techniken gibt es zur Lösung von BIP-Problemen?
Es gibt verschiedene alternative Techniken, die in Verbindung mit dem B&B-Algorithmus eingesetzt werden können, wie z.B. Modellierungstechniken, Techniken der Initialisierung, Branching-Techniken und Bounding-Techniken.
Was ist LPSolve?
LPSolve ist ein Softwarewerkzeug, das zur Lösung von Optimierungsproblemen, einschließlich BIP-Problemen, verwendet werden kann.
Welche Problemgruppen der kombinatorischen Optimierung können als BIP-Modell dargestellt werden?
Problemgruppen der kombinatorischen Optimierung, deren konkrete Probleme sich als BIP-Modell darstellen lassen, umfassen z.B. das Traveling Salesman Problem (TSP), das Set Covering Problem und das Knapsack Problem.
Was sind Beispiele für Fragestellungen im Bereich der Planung fixer Investitionen?
Beispiele für Fragestellungen im Bereich der Planung fixer Investitionen sind: 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?
Was ist die zentrale Frage bei der Standortauswahl?
Die zentrale Frage bei der Standortauswahl ist immer: "Sollte man einen bestimmten Standort für eine bestimmte Einrichtung wählen?"
- Arbeit zitieren
- Raoul Privenau (Autor:in), 2008, Branch-and-Bound-Techniken zur Lösung von BIP-Problemen, München, GRIN Verlag, https://www.grin.com/document/120335
