Das Knapsack-Problem – MarkusHeinemann.com

Zunächst soll das Knapsack-Problem als abstraktes Modell in Google-OR-Tools implementiert werden.

Beschreibung des Knapsack-Problems
Das Knapsack-Problem entspringt der Aufgabe einen Rucksack (engl. Knapsack) mit beschränkter Kapazität zu packen. Dabei können verschieden Gegenstände $i=1,...,I$ entweder eingepackt werden, oder zurückgelassen werden. Für jeden Gegenstand $i$ gibt es im Modell eine Binärvariable $x_{i}$ , die den Wert eins annimmt, wenn der Gegenstand in einer Lösung dem Rucksack zugeordnet wurde.

Kapazitätsrestriktion

Der Rucksack verfügt über eine beschränkte Kapazität $K$ . Jeder Gegenstand nimmt einen bestimmten Anteil der Kapazität in Anspruch. Für Gegenstand $i$ ist dessen Kapazitätsbedarf $g_{i}$ als Parameter vorgegeben.

Als Nebenbedingung ergibt sich daraus:

$\displaystyle\sum_{i=1}^{I} x_{i} \cdot g_{i} \leq K$

Sie stellt sicher, dass nur die Gegenstände in den Rucksack gepackt werden können, die die Kapazität gemeinsam nicht übersteigen.

Dazu ein kleines Beispiel: Es gibt drei Gegenstände Schlafsack: $i=1$ , Waschbeutel: $i=2$ und Winterjacke: $i=3$ . Die Kapazität sei das zulässige Gesamtgewicht, dass der Rucksack haben darf $K=7kg$ . Weiterhin gegeben sind die Gewichte (Kapazitätsbedarf der Gegenstände). Der Schlafsack wiegt $w_1=4kg$ (Naturdaune). Das Gewicht des Waschbeutels ist $w_2=3kg$ und die Winterjacke wiegt $w_3=3kg$ .

Die Kapazitätsrestriktion baut sich nun wie folgt für die drei Gegenstände auf:
$x_1 \cdot w_1 + x_2 \cdot w_2 + x_3 \cdot w_3 \leq K$
Setzt man die Werte ein erhält man:
$x_1 \cdot 4kg + x_2 \cdot 3kg + x_3 \cdot 3kg \leq 7kg$

Wenn man die Gewichte betrachtet, zeigt sich, dass nicht alle drei Gegenstände mitgenommen werden können, wenn Kapazitätsrestriktion eingehalten werden soll. Würde man nun jede der drei Binärvariablen $x_1, x_2, x_3$ auf den Wert eins setzen (alle Gegenstände einpacken), wäre die Kapazität von $7kg$ überschritten.

$4kg + 3kg + 3kg = 10kg$
$10kg \leq 7kg$ – womit die Kapazitätsrestriktion offensichtlich nicht einghalten ist.

Es lassen sich demnach in dieser Beispielinstanz nur zwei der drei Gegenstände des Beispiels mitnehmen. Die zulässigen Lösungen sind:
– Schlafsack und Waschbeutel ( $x_1=1, x_2=1, x_3=0$ )
– Schlafsack und Wintermantel ( $x_1=1, x_2=0, x_3=1$ )
– Waschbeutel und Wintermantel ( $x_1=0, x_2=1, x_3=1$ )
– nur den Schlafsack ( $x_1=1, x_2=0, x_3=0$ )
– nur den Waschbeutel ( $x_1=0, x_2=1, x_3=0$ )
– nur den Wintermantel ( $x_1=0, x_2=0, x_3=1$ )

Zielfunktion
Jeder Gegenstand $i$ im Rucksack hat einen bestimmten Nutzen $u_{i}$ . Die Zielfunktion addiert nun den Nutzen sämtlicher eingepackter Gegenstände. Damit wird versucht, die gegenbene Kapazität bestmöglich auszunutzen.
Die Zielfunktion ergibt sich demnach wie folgt:

$maximiere \, F(x) = \displaystyle\sum_{i=1}^{I} x_{i} \cdot u_{i}$

F ist der Gesamtnutzen, der sich aus einer Lösung ergibt. Dieser Gesamtnutzen soll maximiert werden.
Den höchsten Wert den die Zielfunktion jemals annehmen könnte, wäre die Summe der Nutzenwerte sämtlicher Gegenstände. Dies könnte aber nur eintreten, wenn jeder Gegenstand eingepackt werden könnte. Das wird jedoch ggf. von der Kapazitätsrestriktion verhindert (wie das Beispiel oben zeigt).

Hier nochmal das gesamte Modell:

$max \, F(x) = \displaystyle\sum_{i=1}^{I} x_{i} \cdot u_{i}$
unter den Nebenbedingungen:

$\displaystyle\sum_{i=1}^{I} x_{i} \cdot g_{i} \leq K$
$x_i \in \{0;1\} \, \forall \, i=1,...,I$

Implementation in Google-OR-Tools

Zu Beginn des Programms wird eine Instanz des Solvers importiert.
from ortools.linear_solver import pywraplp

Anschließend werden die Problemdaten definiert. Hier werden die Daten aus dem oben beschriebenen Beispiel verwendet.
Zunächst die Anzahl der Gegenstände $I$ :
I=3
Die Gewichte der Gegenstände ist eine Liste.
g_i=[4,3,3]
Als Nutzwerte für die drei Gegenstände wird 10, 5 und 9 festgelegt.
u_i=[10,5,9]
Die Kapazität des Rucksacks ist 7kg.
K=7
Zur besseren Darstellung werden auch die Namen der Gegenstände als Liste hinterlegt.
Namen_der_Gegenstaende=["Schlafsack","Waschbeutel","Wintermantel"]

Zum Modell:

Jede der drei Binärvariablen wird auch im Python-Modell eine eigene Variable angelegt. Jeder Variable könnte nun ein eigener Name zugeordnet werden. Z.B. „ZuordnenVonGegenstand1“. Der Nachteil daran wäre, dass bei einer großen Anzahl an Variablen das Programmieren extrem aufwendig wäre.

Damit nicht jeder Variable ein eigener Name zugeordnet werden muss, werden die Variablen in einer Liste oder einem Dictionary gesammelt. Das dict ist zwar etwas aufwendiger, erleichtert aber bei großen Modellen enorm den Zugriff. Hier wird gleich das Dictionary verwendet. Jedes Dictionary ist in Python eine Menge aus Paaren von Schlüsselwerten und dazugehörigen Elemente. Das hier verwendete Dictionary heißt „Variablen“. Zunächst wird es initialisiert.

Variablen = {}

Wir verwenden als Schlüssel den Index des Gegenstands um eins reduziert (0,1,2). Eine Schleife läuft alle Elemente von 0 bis I-1 durch (0,1,2).

for i in range(I): Variablen[i] = solver.IntVar(0, 1, 'Gegenstand[%i]' % i)

In jedem Schleifenschritt wird eine ganzzahlige Variable generiert (rechte Seite der Gleichung). Der erste Parameter ist der kleinstmögliche Wert, den die Variable annehmen kann (hier 0). Danach folgt der größtmögliche Wert (1 für Einpacken des Gegenstandes). Der letzte Parameter der Funktion übergibt eine Variablenbezeichnung. Diese lautet hier Gegenstand[%i] für %i setzt Python den aktuellen Indexwert i ein. Jede Variable kann damit eindeutig auseinandergehalten werden. Es ist aber auch ein anderer Variablenname möglich.

Und schon geht’s zur Nebenbedingung. Sie enthält eine Summe über jeden Gegenstand. Diese wird zunächst als Variable „linkeSeite“ gespeichert.

linkeSeite=solver.Sum([g_i[i] * Variablen[i] for i in range(I)])

Dabei wird die Funktion solver.Sum der OR-tools verwendet. Als Parameter erhält sie eine Liste an Variablen. Diese kann man entweder beliebig erstellen, oder wie hier in einer inline Funktion erstellen. Über die bekannten Indizes for i in range(I) wird der jeweilige Gewichtswert mit dem Variablenwert multipliziert (genau wie in der echten Nebenbedingung).

Die Kapazitätsrestriktion wird nun an den Solver übergeben. Das macht die Funktion Solver.Add.

solver.Add(linkeSeite<=K)

Der Parameter K beinhaltet unseren oben definierten Paramter für die Kapazität (K=7).

Zielfunktion
Ganz ähnlich zur Restriktion wird nun die Zielfunktion als eigenes Objekt ZF definiert.

ZF=solver.Sum([Variablen[i] * u_i[i] for i in range(I)])

Anstelle des Gewichtes werden hier die Nutzwerte (jeweils das ite Element aus der Liste u_i) mit dem zugehörigen Variablenwert von i multipliziert.

Zuletzt wird die Optimierungsrichtung festgelegt:

objective=solver.Maximize(ZF)

Und schon beauftragen wir den Solver mit der Lösung des Modells:

solver.Solve()

Hier noch einige Zeilen zur Auswertung der Lösung. Diese beinhalten Ausgabe des Zielfunktionswertes, der benötigten Rechenzeit, Iterationen und der Lösung selbst.

print('Zielfunktionswert:', solver.Objective().Value()) print('WallTime:', solver.WallTime()) print('iterations:', solver.Iterations()) print()


for i in range(I):

 print("Variablenwert Gegenstand %i: %i" % (i,Variablen[i].SolutionValue()))
optimale_Loesung=[]

for i in range(I):

 if Variablen[i].SolutionValue()==1:

  optimale_Loesung.append(Namen_der_Gegenstaende[i])

print("Inhalt des Rucksacks: ",optimale_Loesung )

Hier die fertige Python-Datei zum Download.