Ganzzahlige Optimierung, Branch-and-Bound-Algorithmus

Question 1

Wahr oder falsch?

Bei der ganzzahligen Optimierung ist der Lösungsraum nicht mehr konvex.

Answer 1

Wahr!

vgl. Folie 359

Question 2

Definition: Relaxiertes Problem

Answer 2

Relaxiertes Problem ist ein einfacheres Problem, dessen Lösungsmenge alle Lösungen des Ursprungsproblems enthält. Ferner steht die Lösung des relaxierten Problems in einem nicht-trivialen Zusammenhang mit der Lösung des Ausgangsproblems.

Question 3

Branch-and-Bound-Algorithmus

Wann wird ausgelotet?

Answer 3

Es wird ausgelotet, wenn …

… das Teilproblem optimal ganzzahlig gelöst ist.

… die obere (bzw. untere bei min. Problemen) Schranke eines Teilproblems kleiner (bzw. größer bei min. Problem) als eine bereits gefundene ganzzahlige Lösung ist.

• der zulässige Bereich des Teilproblems unzulässig ist.

Question 4

Nenne die Auswahlregeln für Variablen des Branch-and-Bound-Algorithmus und erkläre sie.

Answer 4

Zufallsauswahl

Fraktionellste Variable (1/2-Regel)
- Wähle diejenige Variable zum einschränken, deren aktueller, nicht ganzzahliger Anteil näher an 1/2 liegt

Strong Branching
- Aufstellung und Berechnung von Teilproblemen für alle nicht ganzzahligen Variablen und schließlich Wahl der Variable, die den ZF-Wert am meisten verändert; Verwerfung der nicht ausgewählten Variablen

Question 5

Nenne die Auswahlstrategien für Teilprobleme des Branch-and-Bound-Algorithmus und erkläre sie.

Answer 5

Maximum Upper Bound (MUB)
- Wähle Problem mit dem besten ZF-Wert aus der Liste

Tiefensuche
- Wähle Problem aus der Liste, welches als letztes eingefügt wurde (LIFO)

Breitensuche
- Wähle Problem aus der Liste, welches als erstes eingefügt wurde (FIFO)

Question 6

Schildern Sie die Grundidee des Branch-And-Bound Algorithmus.

Answer 6

• Lösung einer Folge von relaxierten Problemen, um das ursprüngliche ganzzahlige Problem zu lösen
• Zerlegung des Optimierungsproblems in kleinere Teilprobleme (Branching)
• Entscheidung, welches Teilproblem weitergeführt wird oder durch ein anderes dominiert wird (Bounding)
• Die ganzzahlige, optimale Lösung einer linearen Relaxation eines ganzzahligen Problems kann auch die optimale Lösung des ganzzahligen Problems sein
• Der Zielfunktionswert eines übergeordneten (Teil-)Problems stellt immer eine obere Schranke für die Zielfunktionswerte der untergeordneten Probleme dar

Question 7

Schildern Sie die Grundidee des Gomory Algorithmus.

Answer 7

Beschneidung des Lösungsraums durch weitere NB, sog. Schnittebenen.

Diese NB werden von allen zulässigen, ganzzahligen Lösungspunkten erfüllt.

Momentan optimaler Punkt wird abgeschnitten.