I

Inhaltsverzeichnis

1.  Einleitung.  1

2.  Branch-und-Bound-Methoden.  2

2.1.  Allgemeine Beschreibung der Branch-und-Bound-Methode  2

2.2.  Das Verfahren von Land und Doig.  5

2.2.1.  Die Beschreibung des Verfahrens von Land und Doig.  5

2.2.2.  Der Algorithmus zum Verfahren von Land und Doig  7

2.3.  Das Verfahren von Dakin.  10

2.3.1.  Die Beschreibung des Verfahrens von Dakin.  10

2.3.2.  Der Algorithmus zum Verfahren von Dakin  11

2.3.3.  Zahlenbeispiel.  13

3.  Ganzzahlige Optimierung und das Branch-und-Bound-  

Verfahren   14

3.1.  Vorbemerkung - Probleme mit Ganzzahligkeitsforderungen  14

3.2.  Ein Branch-und-Bound-Verfahren für das Rucksackproblem.  15

3.2.1.  Formulierung des Problems.  15

3.2.2.  Beschreibung des Branch-und-Bound-Verfahrens.  15

4.  Kombinatorische Optimierung und das Branch-und-Bound-  

Verfahren   18

4.1.  Vorbemerkung - Probleme vom kombinatorischen Typ  18

4.2.  Ein Branch-und-Bound-Verfahren für das Rundreiseproblem.  19

4.2.1.  Formulierung des Problems.  19

4.2.2.  Beschreibung des Branch-und-Bound-Verfahrens.  21

4.2.3.  Zahlenbeispiel.  24

4.3.  Ein Branch-und-Bound-Verfahren für das Problem der  

Maschinenbelegungsplanung.   25

4.3.1.  Formulierung des Problems.  25

4.3.2.  Beschreibung des Branch-und-Bound-Verfahrens.  27

4.3.3.  Zahlenbeispiel.  28

5.  Zusammenfassung.  30

Literaturverzeichnis.   31

Anhang A:  Zahlenbeispiel - Verfahren von Land und Doig  33

Anhang B:  Zahlenbeispiel - Verfahren von Dakin.  35

Anhang C:  Zahlenbeispiel - Rucksackproblem  37

Anhang D: Flussdiagramm des Branch-und-Bound-Algorithmus für

Anhang E: Zahlenbeispiel - Rundreiseproblem.............................................39

Anhang F: Zahlenbeispiel - Maschinenbelegungsplanung............................45

Abbildungsverzeichnis.....................................................................................47

1. Einleitung

Eine Vielzahl der Aufgabenstellungen des Operations Research führen auf

Probleme mit Ganzzahligkeitsbedingungen. Diese Optimierungsprobleme

:

- Probleme mit Unteilbarkeitsbedingungen,

- Kombinatorische Probleme,

- Überdeckungsprobleme und andere Probleme aus der diskreten

Netzoptimierung,

- Verteilungsprobleme.

Die scheinbare Einfachheit der Problemstellungen kann bei der Lösung mit

.

- Grafisches Verfahren,

- Schnittebenen-Verfahren,

- Entscheidungsbaum-Verfahren,

- Heuristische Verfahren.

Die praktische Relevanz dieser Methoden hängt wesentlich von der

Effizienz der Auffindung einer Lösung ab.

Das Branch-und-Bound-Verfahren hat sich als ein exaktes Verfahren zur

Lösung einer Vielzahl von großen ganzzahligen und kombinatorischen

Problemen bewährt.

In der vorliegenden Arbeit werden die grundlegendsten Branch-und-Bound-

Verfahren in ihren Wesenszügen erläutert und ihre Realisierung anhand von

Beispielen aus der ganzzahligen und kombinatorischen Optimierung

.

Vgl. KORBUT/FINKELSTEIN S. 7-8.

2

Vgl. Ebenda, S. VI.

3

Vgl. ZIMMERMANN, S. 125.

4

Selbstverständlich kann die Arbeit den Anspruch auf eine umfassende Beschreibung aller

bekannten Branch-und-Bound-Verfahren und eine Darstellung aller vorstellbaren

praktischen Anwendungen nicht erheben.

2. Branch-und-Bound-Methoden

2.1. Allgemeine Beschreibung der Branch-und-Bound-Methode

Im allgemeinen lässt sich das Branch-und-Bound-Verfahren wie folgt

kann oder nicht. Wird dabei festgestellt, dass sich die optimale Lösung nicht

in der gerade betrachteten Klasse befinden kann, kann diese ganze Klasse

von den weiteren Untersuchungen ausgeschlossen werden. Diese implizite

Ein Branch-und-Bound-Verfahren setzt sich aus vier Hauptteilen

zusammen:

-der Relaxation

-der Separation

-der Schrankenberechnung und

-der Auswahlregel.

Die Relaxation dient dazu, zu dem schwer lösbaren Problem ein leichter

lösbares anzugeben, so dass alle zulässigen Punkte des schwer lösbaren

Problems auch zulässig für das leichter lösbare Problem sind. Handelt es

sich um ein (gemischt-) ganzzahliges Problem, so wird beispielsweise der

genommen. Als Relaxation für ein Rundreiseproblem kann man sich mit

einem Zuordnungsproblem (z.B. der Ungarischen Methode) bedienen.

Die Separation gibt an, wie eine Menge in Teilmengen zerlegt (Branching)

werden soll. Dabei kann man die Aufspaltung in nur zwei Teilmengen oder

bis hin in alle zulässigen Punkten erfolgen. Die Art der Aufspaltung in

Vgl. BURKARD (1987), S. 379ff.

6

Es wird nur implizit nachgewiesen, ob die untersuchte Klasse als optimal Lösung in Frage

kommen kann. Somit liegt der Vorteil der impliziten Enumeration gegenüber der

vollständigen Enumeration auf der Hand.

Bei der Schrankenberechnung wird je nach Problemart, Maximierungs- oder

Minimierungsproblem, eine obere oder untere Schranke (Bound) ermittelt.

Dieser Bound wird aus den Zielfunktionswerten der behandelten Teilmenge

(Klasse) bestimmt.

, ist es erforderlich, eine Reihenfolge der Abarbeitung der

Teilmengen festzulegen. Die Auswahlregel gibt an, welche noch zu untersuchende Teilmenge als nächste behandelt werden soll. Die

bekanntesten Auswahlregeln sind:

-die LIFO-Regel bzw. die neueste Schranken (newest bound)-Regel

und

Teilmenge so lange weiter untersucht wird, bis sie ausgeschieden werden muss.

Die beste Schranken-Regel wählt die Teilmenge aus, die die günstigste

Formell lässt sich die obige allgemeine Beschreibung des Branch-und-

:

Gegeben sei ein ganzzahliges lineares Problem

Die Relaxation von (2.1):

Die Verzweigung wird mit dem folgenden Mehrschrittverfahren durch- geführt.

Ausnahme bildet die Möglichkeit einer Parallelisierung des Branch-und-Bound-

Verfahrens. In SCHWARTZ S. 213ff. wird für das Problem der gemischt-ganzzahligen

Optimierung der Produktionsplanung gezeigt, dass sich die Effizienz durch entsprechende

Parallelisierung der Effizienz von Vektor-Supercomputern annähert.

8

Die günstigste Schranke ist bei einem Minimierungsproblem die kleinste untere Schranke.

Im Falle einer Maximierung ist sie die größte obere Schranke. In BURKARD (1987), S. 384

wird einschränkender Weise nur über die Regel der größten Schranke gesprochen. Die

etwas korrektere Bezeichnung der Regel ist eben die beste Schranken-Regel (Vgl.

HILLIER/LIEBERMANN S. 390.).

9

Vgl. KORBUT/FINKELSTEIN S. 160ff.

Abb. 2.1. Zerlegung des Problems in Teilmengen.

Wird das Problem

gelöst, so seien x*(k) die entsprechenden Maximallösungen. Gibt es ein

Von den weiteren Betrachtungen können alle jene Teilmengen

ausgeschlossen werden, für die

gilt.

Im wesentlichen sind die Verfahren von Land und Doig, von Dakin sowie

von Driebeek die grundlegendsten Branch-und-Bound-Verfahren zur

Lösung von (gemischt-) ganzzahligen Problemen. Die einzelnen Methoden

-in der Art und Weise, wie verzweigt wird und

-in der Auswahl der Knoten, zu dem im nachfolgenden Schritt

verzweigt werden soll.

ihren Grundzügen erläutert werden.

2.2. Das Verfahren von Land und Doig

2.2.1. Die Beschreibung des Verfahrens von Land und Doig

zur Lösung gemischt-ganzzahliger, linearer Probleme. In der

Vorgehensweise gibt es keinen Unterschied, ob es sich um ein rein-

ganzzahliges oder gemischt-ganzzahliges Problem handelt.

Es wird zunächst das lineare Problem ohne Berücksichtigung der

Ganzzahligkeitsbedingung gelöst:

Die Optimallösung davon sei x*(1). Verletzt eine Komponente von x*(1),

bedingung, dann werden zwei neue lineare Programme (P2) und (P3) aufgestellt:

Ganzzahligkeitsbedingung, so muss dieser Knoten verzweigt werden:

Vgl. BURKARD (1972), S. 173.

11

Die Methode von Driebeek wird hier nicht weiter betrachtet, weil sie zur Lösung von

großen gemischt-ganzzahligen linearen Problemen mit nur wenigen ganzzahligen Variablen

geeignet (Vgl. BURKARD (1972), S. 185ff., oder BEISEL/MENDEL, S. 290ff.).

12

Vgl. LAND/DOIG, S. 497-520 und BURKARD (1972), S. 173-180.

aufgestellt. Damit wird sichergestellt, dass das Maximum der optimalen

Zielfunktionswerte jener linearer Programme, die den Endknoten

aufgestellten linearen Programmes. Die Verzweigung wird in Abb. 2.2

dargestellt.

Abb. 2.2: Verzweigung im zweiten Schritt.

Das Kriterium zur Auswahl der Knoten im Graph wird der größte Wert der

Zielfunktion in den Endknoten verwendet. Der durch das Auswahlkriterium

verzweigt werden.

Die Verzweigung, d.h., Generierung drei neuer linearer Programme (P(k)),

P(t)) und (P(m)), wird nach folgender Regel durchgeführt:

2.2.2. Der Algorithmus zum Verfahren von Land und Doig

Für das Optimierungsproblem (P):

lässt sich der Algorithmus des Branch-und-Bound-Verfahrens von Land und

.

Anfangsdaten:

A (mxn)-Matrix,

k Indizes der ganzzahligen Variablen,

j := 1,

Konstante festgehalten werden,

1. Löse für λ := j-t, ..., j die linearen Programme

Hat das lineare Programm eine endliche Lösung x*(λ), so setze

Andernfalls setze f(λ) := 1.

Gehe zu 2.

Vgl. BURKARD (1972), S. 177f.