HUMBOLDT-UNIVERSITÄT ZU BERLIN
MATHEMATISCH-NATURWISSENSCHAFTLICHE FAKULTÄT II
INSTITUT FÜR MATHEMATIK
PROF. PHD. ANDREAS GRIEWANK
JAN RIEHME
[width=3cm]huk


Humboldt-Universität zu Berlin, Institut für Mathematik, Unter den Linden 6, D-10099 Berlin



Material zum Rucksackproblem

(Aufgabe 6 in Serie 4)


Inhalt

Rucksackprobleme

Gegebene Daten

Problemstellung: Rucksackproblem mit oberen Schranken

Finde Häufigkeiten $ x^*=(x_1^*,\dots,x_n^*)^T\in Z\!\!\!Z_+^n$ der Gegenstände $ G_i, i=1,\dots,n$, die den Wert $ w^T x^*$ der in den Rucksack gepackten Gegenstände maximiert, ohne dabei das Volumen des Rucksacks zu überschreiten ( $ v^T x^* \le V$) und ohne die Vorratsbedingungen $ x^* \le b$ zu verletzen.

Mathematisches Modell: Rucksackproblem mit oberen Schranken

Ganzzahliges Lineares Optimierungsproblem

\begin{displaymath} \begin{array}{rcrcl} z = w^Tx & \longrightarrow & \max \\ [... ...in Z\!\!\!Z_+, v,b\in Z\!\!\!Z_+^n, w\in I\!\!R_+^n \end{array}\end{displaymath}

Bemerkung: Das ist ein Rucksackproblem mit oberen Schranken $ b_i$ für die Häufigkeiten $ x_i$ der Gegenstände $ G_i$ und nur eine mögliche Form eines Rucksackproblems. Andere wichtige Arten von Rucksackproblemen sind:

Zum Teil kann man durch einfache Transformationen eine Form des Rucksackproblems in eine andere überführen. So kann man z.Bsp. obiges Rucksackproblem mit oberen Schranken $ b_i$ durch Einführung von Gegenständen $ \overline{G}_j$ und zugehörigen binären Variablen $ y_j$, $ j=1,\dots,m_n$ mit $ m_k=\sum_{i=1}^k b_i$ und $ \overline{w}_j = w_{\overline{i}}$, $ \overline{v}_j = v_{\overline{i}}$ wobei $ \overline{i}(j) = argmax \{ k=1,\dots,n\,\vert\, j \le m_k = \sum_{i=1}^k b_i\}$ in ein Binäres Rucksackproblem umwandeln. Man hat also für jedes mögliche Exemplar des Gegenstandes $ G_i$ eine eigene Variable $ y_j$, $ m_{j-1} < j \le m_j$ mit $ m_0=0$, eingeführt. Das entsprechende binäre Rucksackproblem lautet nun:

\begin{displaymath} \begin{array}{rcrcl} \max & \sum_{j=1}^{m_n} \overline{w}_j... ...!\!\!Z, \overline{w}_j\in I\!\!R, 1\le j \le m_n \end{array}\end{displaymath}

Aus der Lösung $ y^*\in\{ 0, 1\}^{m_n}$ des binären Problems kann man wie folgt eine Lösung des Ausgangsproblems mit oberen Schranken konstruieren:

$\displaystyle x^*_i = \sum_{m_{i-1}+1}^{m_i} y^*_i $

Voraussetzungen

Im Folgenden wird ein einfacher spezieller Algorithmus1 zur Lösung des Rucksackproblems mit oberen Schranken für die Variablen $ x_i$ angegeben. Dabei setzen wir insbesondere eine Sortierung der Gegenstände $ G_i$ nach abnehmenden Quotienten $ \frac{w_i}{v_i}$ voraus, es soll also gelten:

$\displaystyle \frac{w_1}{v_1} \ge \frac{w_2}{v_2} \ge \dots \ge \frac{w_n}{v_n}. $

Mit anderen Worten: Der erste Gegenstand hat den höchsten Wert pro Volumeneinheit, der letzte den kleinsten Wert.

Falls die Daten nicht dieser Sortierungsbedingung genügen, dann muss vor dem Anwerfen des Algorithmus entsprechend sortiert werden. Im Folgenden gehen wir davon aus, dass die Sortierung nach fallendem Wert pro Volumeneinheit vorliegt.

Greedy - Heuristik

Der Name ,,gefräßig`` beschreibt das Vorgehen dieses einfachen Näherungsalgorithmus2 sehr gut: Von dem am meisten Wert pro Volumeneinheit versprechenden Gegenstand werden soviele Exemplare wie möglich eingepackt und dann das verbleibende Volumen mit dem nächstbesten Gegenstand gefüllt. Die Anzahl, wie oft ein Gegenstand $ G_i$ eingepackt werden kann ist dabei begrenzt durch das verfügbare (Rest)volumen $ \ensuremath{\tilde V}$ und die maximale Anzahl $ b_i$:

$\displaystyle x_i = \min \left\{ \left\lfloor \frac \ensuremath{\tilde V}{v_i} \right\rfloor, b_i \right\}, $

wobei $ \lfloor a \rfloor = \max \{k\in Z\!\!\!Z\,\vert\, k \le a \} $ die größte ganze Zahl bezeichnet, die kleiner als $ a\in I\!\!R$ ist.


\begin{algorithm} % latex2html id marker 132\caption{Greedy -- Heuristik f\um... ...{\tilde V}- v_i * g_i$ \EndFor \EndProcedure \end{algorithmic}\end{algorithm}

Der Wert der Greedy-Lösung berechnet sich als $ \sum_{i=1}^n w_i g_i$. Beachtenswert ist noch, dass die Werte $ w_i$ der Gegenstände erst bei der Berechnung des Wertes gebraucht werden nicht aber zur Bestimmung der Greedy-Lösung $ g\in Z\!\!\!Z_+^n$ (das liegt an der speziellen Sortierung und den darauf abgestimmten Algorithmus, der den Wert nicht mit berechnet).

Ein spezieller Branch & Bound - Algorithmus für das Rucksackproblem mit oberen Schranken

Schranken

Schranken (engl. bounds) werden im Branch & Bound - Verfahren benutzt, um Teilprobleme zu bewerten, die durch die Verzweigung (engl. branch) entstanden sind: Bei einem $ \max$ - Problem wie dem Rucksackproblem will man durch die Schranke erfahren, ob die Abarbeitung eines Teilproblems keine bessere Lösung als die bisher beste gefundene Lösung liefern kann. Wenn das so ist, dann muss dieses Teilproblem nicht weiter untersucht werden (Schritt 6 im Algorithmus aus der Vorlesung).


Im vorliegenden Fall von nach fallendem Wert pro Volumeneinheit sortierten Gegenständen erhält man sehr einfach zu berechnende obere Schranken3:

\begin{displaymath} \begin{array}[h]{lcl} B_1(\ensuremath{\tilde V},i) &=& \ens... ...a v_i}{v_{i+1}} \right\rfloor, b_{i+1} \right\}\\ \end{array}\end{displaymath}

Die erste Schranke füllt das komplette zur Verfügung stehende Volumen $ \ensuremath{\tilde V}$ mit dem $ i$-ten Gegenstand, und zwar ohne Rücksicht auf den Vorrat $ b_i$ und Ganzzahligkeitsforderung. Diese beiden Relaxationen führen dazu, dass der Wert $ B_1(\ensuremath{\tilde V},i)$ immer größer oder gleich dem optimalen Wert des Rucksackproblems mit dem Volumen $ \ensuremath{\tilde V}$ und den Gegenständen $ G_i, G_{i+1},\dots,G_n$ ist. Damit ist $ B_1(\ensuremath{\tilde V},i)$ eine obere Schranke für den aus dem Volumen $ \tilde V$zu erwartenden maximalen Wert.

Die beiden Schranken $ B_2(\ensuremath{\tilde V},i)$ und $ B_3(\ensuremath{\tilde V},i)$ sind verbesserte obere Schranken, d.h. es gilt

$\displaystyle B_1(\ensuremath{\tilde V},i) \ge B_2(\ensuremath{\tilde V},i) \ge B_3(\ensuremath{\tilde V},i). $

Die Verkleinerung der Schranke wird dabei durch eine weniger starke Relaxation erreicht, indem ein bzw. zwei Gegenstände ($ G_i$ und $ G_{i+1}$) maximal oft unter Beachtung der entsprechenden Vorräte und der Ganzzahligkeit benutzt werden. Das jeweils verbleibende Volumen wird dann mit dem nächsten Gegenstand (also $ G_{i+1}$ bzw. $ G_{i+2}$) vollständig ausgefüllt (nun wieder ohne Vorrat und Ganzzahligkeit zu beachten). Allerdings werden die Verbesserungen der Schranken durch einen höheren Berechnungsaufwand erkauft.

Ob der höhere Aufwand bei der Schrankenberechnung gerechtfertigt ist oder nicht kann nicht im Voraus gesagt werden. Der Erfolg der Schranken hängt unter anderem von der Größe des Problems (Anzahl der Gegenstände), aber auch von den Daten (z.Bsp. Volumen des Rucksacks) und der sich daraus ergebenden Verzweigungsstruktur ab.

Bei der Berechnung der verbesserten Schranken ist zu beachten, dass $ B_2(\ensuremath{\tilde V},i)$ nur für $ i=1,\dots,n-1$ und $ B_3(\ensuremath{\tilde V},i)$ nur für $ i=1,\dots,n-2$ definiert sind. Bei der Implementation kann man entsprechende Falluntescheidungen aber vermeiden, wenn man Hilfsgegenstände $ G_{n+1}$ und $ G_{n+2}$ einführt mit

$\displaystyle v_{n+1} = v_{n+2} = 1, \qquad w_{n+1} = w_{n+2} = 0, \qquad b_{n+1} = b_{n+2} = 0. $

Algorithmus

Ein einfaches Branch & Bound - Verfahren ist in Algorithmus 2 angegeben. Die benutzte rekursive Schreibweise erlaubt eine einfache Notation.


\begin{algorithm} % latex2html id marker 194 [h] \caption{Branch \& Bound f\uml... ...siver Aufruf}} \EndIf \EndFor \EndProcedure \end{algorithmic}\end{algorithm}

Der Aufruf dieser rekursiven Routine hat dabei folgendermaßen zu geschehen:
\begin{algorithmic}[1] \State $x = 0,\; x^* = 0$\ \Comment{Vektoren auf Null se... ...b,x,z,x^*,z^*$) \Comment{\textcolor{red}{Rekursiver Aufruf}} \end{algorithmic}

Beispiele

$ V = 26 ,\quad n = 3, \quad v=(3,5,7)^T,\quad w=(6,8,10)^T, \quad, b=(4,3,2)^T$

          Benutztes Anzahl Anzahl Anzahl
          Volumen Schranken- Schleifenkörper- rekursiver
  $ z^*$ $ x_1^*$ $ x_2^*$ $ x_3^*$ $ v^T x^*$ berechnung durchläufe Aufrufe
Greedy 40 4 2 0 22      
Voll.Enum. 44 4 0 2 26 0 68 25
B&B, $ B_1$ 44 4 0 2 26 17 25 9
B&B, $ B_2$ 44 4 0 2 26 14 19 6
B&B, $ B_3$ 44 4 0 2 26 13 17 5


$ V = 276 ,\quad n = 3, \quad v=(3,5,7)^T,\quad w=(6,8,10)^T, \quad, b=(14,33,32)^T$

          Benutztes Anzahl Anzahl Anzahl
          Volumen Schranke Schleifenkörper- rekursiver
  $ z^*$ $ x_1^*$ $ x_2^*$ $ x_3^*$ $ v^T x^*$ wirksam durchläufe Aufrufe
Greedy 438 14 33 0 270      
Voll.Enum. 444 14 30 12 276 0 13150 526
B&B, $ B_1$ 444 14 30 12 276 507 526 20
B&B, $ B_2$ 444 14 30 12 276 134 141 8
B&B, $ B_3$ 444 14 30 12 276 114 119 6


Fußnoten

... Algorithmus1
In der Vorlesung wurde ein allgemeiner B&B - Algorithmus angegeben, hier werden wir zwar Grundkenntnisse über B&B aus der Vorlesung voraussetzen, ansonsten aber einen einfachen Algorithmus speziell für das Rucksackproblem mit oberen Schranken erarbeiten. Weiterhin ist zu beachten, dass in der Vorlesung ein B&B-Algorithmus für Minimierungsprobleme angegeben wurde, hier aber maximiert wird. Das heißt z.Bsp. dass hier obere und nicht untere Schranken für Teilprobleme benötigt werden.
... Näherungsalgorithmus2
Eine Heuristik ist ein Verfahren, das für eine Problemklasse in vielen Fällen ziemlich gute Resultate liefert, allerdings ist dabei Optimalität nicht garantiert. Meist beruhen Heuristiken auf einfachen Beobachtungen an einigen Beispielen. Oft erhält man mit diesen im Vergleich zu exakten Verfahren (die die Optimalität garantieren) sehr einfachen Algorithmen sehr gute Resultate in einem Bruchteil der Rechenzeit exakter Verfahren.
... Schranken3
Das ist nicht immer der Fall, oft ist die Schrankenberechnung viel teurer als hier, z.Bsp. kann die Schrankenberechnung die Lösung eines Linearen Optimierungsproblems bedeuten.

2006-01-31