Übung 08: Branch & Bound

Grundlagen Operations Research

Video zur Übung

Aufgabe 1

Gegeben sei folgendes ganzzahlige Optimierungsproblem:

maximiere F=X1+2X2+3X3u.d.N.2X1+X2≤173X2+3X3≤13X1,X2,X3≥0 und ganzzahlig \begin{aligned} \text{maximiere } \; & F = X_1 + 2 X_2 + 3 X_3 \\ \text{u.d.N.} \quad & 2 X_1 + X_2 \le 17 \\ & 3 X_2 + 3 X_3 \le 13 \\ & X_1, X_2, X_3 \ge 0 \text{ und ganzzahlig} \end{aligned}

Im Rahmen eines Branch-&-Bound-Verfahrens wurden die zusätzlichen Restriktionen X2≥1X_2 \ge 1 und X2≤1X_2 \le 1 eingeführt, also X2=1X_2 = 1.

  1. Bestimmen Sie eine obere Schranke für das zugehörige Teilproblem.
  2. Lösen Sie das ganzzahlige Teilproblem grafisch.
  3. Überprüfen Sie Ihre Lösungen mit Julia.

Ihre Lösung in Julia

Modellieren Sie zunächst die LP-Relaxation des Teilproblems (X2=1X_2 = 1 fixieren Sie mit fix(modell[:X][2], 1; force = true)) und nennen Sie das Modell modell und die Variablen X:

using JuMP, HiGHS

modell = Model(HiGHS.Optimizer)
set_silent(modell)

# IHR CODE HIER

optimize!(modell)
# Ergebnisse ausgeben, z. B. @show value(X1) oder @show value.(X)
# Führen Sie diese Zelle nach Ihrer Lösung aus:
@assert isapprox(objective_value(modell), 20.0; atol = 1e-4) "Noch nicht korrekt, ist X2 auf 1 fixiert und das Problem noch nicht ganzzahlig?"
println("Obere Schranke korrekt: F = ", objective_value(modell))

Das ganzzahlige Teilproblem

Deklarieren Sie die Variablen nun ganzzahlig (Int) und lösen Sie erneut, das Ergebnis muss zu Ihrer grafischen Lösung passen:

@assert isapprox(objective_value(modell), 19.0; atol = 1e-4) "Noch nicht korrekt, sind alle Variablen ganzzahlig deklariert?"
println("Ganzzahliges Teilproblem korrekt: F = ", objective_value(modell))

Aufgabe 2

Gegeben sei der folgende Branch-&-Bound-Baum. Jeder Kasten zeigt den Namen des Teilproblems, die Schranke F‾i\bar{F}_i und die Lösung (X1,X2,X3,X4)(X_1, X_2, X_3, X_4):

Branch-&-Bound-Baum, an jeder Kante ein Fragezeichen; je Teilproblem Schranke und Lösung (X1; X2; X3; X4), Nachfolger links vor rechts: Pa 700 (0,3; 1; 1; 0,8) verzweigt in Pb 650 (0; 1; 1; 0,2) und Pc 660 (1; 1; 0,4; 0). Pb in Pd 600 (0; 1; 1; 0) und Pe 610 (0; 1; 0,08; 1). Pc in Pf 615 (1; 1; 0; 0) und Pg 640 (1; 0,5; 1; 0). Pe in Ph 570 (0; 1; 0; 1) und Pi 530 (0; 0; 1; 1). Pg in Pj 620 (1; 0; 1; 0) und Pk (unzulässig).

  1. Was für ein Variablentyp wird betrachtet?

  2. Handelt es sich um eine Maximierung oder eine Minimierung?

  3. Ersetzen Sie die Fragezeichen durch die zugehörigen Variablenfestlegungen.

  4. Welche Regel wurde bei der Variablenauswahl angewandt?

  5. Bestimmen Sie die Reihenfolge der Abarbeitung der Teilprobleme bei reiner Tiefensuche, bei Tiefensuche mit MUB und bei Breitensuche (vgl. Vorlesung 8).