Google-OR-Tools

2 Beiträge

Das Knapsack-Problem

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.

Google OR-Tools einfach erklärt (Teil I – Einführung und Installation)

Hier soll eine Einführung in die Open-Source Optimierungssoftware Google-OR-Tools gegeben werden. Dieses sehr gute Bundle an Optimierungssoftware umfasst unter anderem eine eigene Modellierungssprache als auch einen Standardsolver. Diese Beitragsreihe konzentriert sich auf diese beiden Elemente. Dazu sollen Erklärungen von Einrichtung über Modellierung bis hin zur Lösung präsentiert werden und mit einfachen Beispielen ergänzt werden.

Voraussetzungen und Installation
Um Googles OR-Tools verwenden zu können, benötigt man eine Entwicklungsumgebung. Neben dem hier verwendeten Anaconda (Python 3.7) funktioniert auch Microsoft .net und C++. Wichtig: es muss eine 64bit Version des Python-Frameworks verwendet werden, sonst lassen sich die OR-tools nicht wie hier beschrieben installieren.

Anaconda lässt sich von deren Webseite kostenlos beziehen. Nach erfolgreicher Installation können Google-Or-Tools direkt per Befehl hinzugefügt werden.

Anleitung für Windows:
Nach einem Klick auf das Startmenü (Windowslogo): “Anaconda Promt” eingeben und das Programm starten
Im neuen Fenster folgendes eingeben:
pip install ortools

Bei erfolgreicher Installation erscheint unter anderem:
Installing collected packages: protobuf, ortools
Successfully installed ortools-6.9.5824 protobuf-3.6.1

Damit ist die Installation abeschlossen und die Modellierung kann beginnen!