{"id":596,"date":"2018-11-11T20:42:12","date_gmt":"2018-11-11T18:42:12","guid":{"rendered":"https:\/\/markusheinemann.com\/wordpress\/?p=596"},"modified":"2018-11-12T00:12:11","modified_gmt":"2018-11-11T22:12:11","slug":"das-knapsack-problem","status":"publish","type":"post","link":"https:\/\/markusheinemann.com\/wordpress\/?p=596","title":{"rendered":"Das Knapsack-Problem"},"content":{"rendered":"

Zun\u00e4chst soll das Knapsack-Problem als abstraktes Modell in Google-OR-Tools implementiert werden.<\/p>\n

Beschreibung des Knapsack-Problems<\/strong>
\nDas Knapsack-Problem entspringt der Aufgabe einen Rucksack (engl. Knapsack) mit beschr\u00e4nkter Kapazit\u00e4t zu packen. Dabei k\u00f6nnen verschieden Gegenst\u00e4nde \"i=1,...,I\" entweder eingepackt werden, oder zur\u00fcckgelassen werden. F\u00fcr jeden Gegenstand \"i\" gibt es im Modell eine Bin\u00e4rvariable \"x_{i}\", die den Wert eins annimmt, wenn der Gegenstand in einer L\u00f6sung dem Rucksack zugeordnet wurde.<\/p>\n

Kapazit\u00e4tsrestriktion<\/strong><\/p>\n

Der Rucksack verf\u00fcgt \u00fcber eine beschr\u00e4nkte Kapazit\u00e4t \"K\". Jeder Gegenstand nimmt einen bestimmten Anteil der Kapazit\u00e4t in Anspruch. F\u00fcr Gegenstand \"i\" ist dessen Kapazit\u00e4tsbedarf \"g_{i}\" als Parameter vorgegeben.<\/p>\n

Als Nebenbedingung ergibt sich daraus:<\/p>\n

\"\displaystyle\sum_{i=1}^{I} x_{i} \cdot g_{i} \leq K\"<\/p>\n

Sie stellt sicher, dass nur die Gegenst\u00e4nde in den Rucksack gepackt werden k\u00f6nnen, die die Kapazit\u00e4t gemeinsam nicht \u00fcbersteigen.<\/p>\n

Dazu ein kleines Beispiel:<\/strong> Es gibt drei Gegenst\u00e4nde Schlafsack: \"i=1\", Waschbeutel: \"i=2\" und Winterjacke: \"i=3\". Die Kapazit\u00e4t sei das zul\u00e4ssige Gesamtgewicht, dass der Rucksack haben darf \"K=7kg\". Weiterhin gegeben sind die Gewichte (Kapazit\u00e4tsbedarf der Gegenst\u00e4nde). Der Schlafsack wiegt \"w_1=4kg\" (Naturdaune). Das Gewicht des Waschbeutels ist \"w_2=3kg\" und die Winterjacke wiegt \"w_3=3kg\".<\/p>\n

Die Kapazit\u00e4tsrestriktion baut sich nun wie folgt f\u00fcr die drei Gegenst\u00e4nde auf:
\n\"x_1 \cdot w_1 + x_2 \cdot w_2 + x_3 \cdot w_3 \leq K\"
\nSetzt man die Werte ein erh\u00e4lt man:
\n\"x_1 \cdot 4kg + x_2 \cdot 3kg + x_3 \cdot 3kg \leq 7kg\"<\/p>\n

Wenn man die Gewichte betrachtet, zeigt sich, dass nicht alle drei Gegenst\u00e4nde mitgenommen werden k\u00f6nnen, wenn Kapazit\u00e4tsrestriktion eingehalten werden soll. W\u00fcrde man nun jede der drei Bin\u00e4rvariablen \"x_1, x_2, x_3\" auf den Wert eins setzen (alle Gegenst\u00e4nde einpacken), w\u00e4re die Kapazit\u00e4t von \"7kg\" \u00fcberschritten.<\/p>\n

\"4kg + 3kg + 3kg = 10kg\"
\n\"10kg \leq 7kg\" – womit die Kapazit\u00e4tsrestriktion offensichtlich nicht einghalten ist.<\/p>\n

Es lassen sich demnach in dieser Beispielinstanz<\/strong> nur zwei der drei Gegenst\u00e4nde des Beispiels mitnehmen. Die zul\u00e4ssigen L\u00f6sungen sind:
\n– Schlafsack und Waschbeutel (\"x_1=1, x_2=1, x_3=0\")
\n– Schlafsack und Wintermantel (\"x_1=1, x_2=0, x_3=1\")
\n– Waschbeutel und Wintermantel (\"x_1=0, x_2=1, x_3=1\")
\n– nur den Schlafsack (\"x_1=1, x_2=0, x_3=0\")
\n– nur den Waschbeutel (\"x_1=0, x_2=1, x_3=0\")
\n– nur den Wintermantel (\"x_1=0, x_2=0, x_3=1\")<\/p>\n

Zielfunktion<\/strong>
\nJeder Gegenstand \"i\" im Rucksack hat einen bestimmten Nutzen \"u_{i}\". Die Zielfunktion addiert nun den Nutzen s\u00e4mtlicher eingepackter Gegenst\u00e4nde. Damit wird versucht, die gegenbene Kapazit\u00e4t bestm\u00f6glich auszunutzen.
\nDie Zielfunktion ergibt sich demnach wie folgt:<\/p>\n

\"maximiere \, F(x) = \displaystyle\sum_{i=1}^{I} x_{i} \cdot u_{i}\"<\/p>\n

F ist der Gesamtnutzen, der sich aus einer L\u00f6sung ergibt. Dieser Gesamtnutzen soll maximiert werden.
\nDen h\u00f6chsten Wert den die Zielfunktion jemals annehmen k\u00f6nnte, w\u00e4re die Summe der Nutzenwerte s\u00e4mtlicher Gegenst\u00e4nde. Dies k\u00f6nnte aber nur eintreten, wenn jeder Gegenstand eingepackt werden k\u00f6nnte. Das wird jedoch ggf. von der Kapazit\u00e4tsrestriktion verhindert (wie das Beispiel oben zeigt).<\/p>\n

Hier nochmal das gesamte Modell:<\/p>\n

\"max \, F(x) = \displaystyle\sum_{i=1}^{I} x_{i} \cdot u_{i}\"
\nunter den Nebenbedingungen:<\/p>\n

\"\displaystyle\sum_{i=1}^{I} x_{i} \cdot g_{i} \leq K\"
\n\"x_i \in \{0;1\} \, \forall \, i=1,...,I\"<\/p>\n

 <\/p><\/blockquote>\n

Implementation in Google-OR-Tools<\/strong><\/p>\n

Zu Beginn des Programms wird eine Instanz des Solvers importiert.
\nfrom ortools.linear_solver import pywraplp<\/code><\/p>\n

Anschlie\u00dfend werden die Problemdaten definiert. Hier werden die Daten aus dem oben beschriebenen Beispiel verwendet.
\nZun\u00e4chst die Anzahl der Gegenst\u00e4nde \"I\":
\nI=3<\/code>
\nDie Gewichte der Gegenst\u00e4nde ist eine Liste.
\ng_i=[4,3,3]<\/code>
\nAls Nutzwerte f\u00fcr die drei Gegenst\u00e4nde wird 10, 5 und 9 festgelegt.
\nu_i=[10,5,9]<\/code>
\nDie Kapazit\u00e4t des Rucksacks ist 7kg.
\nK=7<\/code>
\nZur besseren Darstellung werden auch die Namen der Gegenst\u00e4nde als Liste hinterlegt.
\nNamen_der_Gegenstaende=[\"Schlafsack\",\"Waschbeutel\",\"Wintermantel\"]<\/code><\/p>\n

Zum Modell:<\/p>\n

Jede der drei Bin\u00e4rvariablen wird auch im Python-Modell eine eigene Variable angelegt. Jeder Variable k\u00f6nnte nun ein eigener Name zugeordnet werden. Z.B. „ZuordnenVonGegenstand1“. Der Nachteil daran w\u00e4re, dass bei einer gro\u00dfen Anzahl an Variablen das Programmieren extrem aufwendig w\u00e4re.<\/p>\n

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\u00dfen Modellen enorm den Zugriff. Hier wird gleich das Dictionary verwendet. Jedes Dictionary ist in Python eine Menge aus Paaren von Schl\u00fcsselwerten und dazugeh\u00f6rigen Elemente. Das hier verwendete Dictionary hei\u00dft „Variablen“. Zun\u00e4chst wird es initialisiert.<\/p>\n

Variablen = {}<\/code><\/p>\n

Wir verwenden als Schl\u00fcssel den Index des Gegenstands um eins reduziert (0,1,2). Eine Schleife l\u00e4uft alle Elemente von 0 bis I-1 durch (0,1,2).<\/code><\/p>\n

for i in range(I):
\n Variablen[i] = solver.IntVar(0, 1, 'Gegenstand[%i]' % i)<\/code><\/p>\n

In jedem Schleifenschritt wird eine ganzzahlige Variable generiert (rechte Seite der Gleichung). Der erste Parameter ist der kleinstm\u00f6gliche Wert, den die Variable annehmen kann (hier 0). Danach folgt der gr\u00f6\u00dftm\u00f6gliche Wert (1 f\u00fcr Einpacken des Gegenstandes). Der letzte Parameter der Funktion \u00fcbergibt eine Variablenbezeichnung. Diese lautet hier Gegenstand[%i] f\u00fcr %i setzt Python den aktuellen Indexwert i ein. Jede Variable kann damit eindeutig auseinandergehalten werden. Es ist aber auch ein anderer Variablenname m\u00f6glich.<\/p>\n

Und schon geht’s zur Nebenbedingung. Sie enth\u00e4lt eine Summe \u00fcber jeden Gegenstand. Diese wird zun\u00e4chst als Variable „linkeSeite“ gespeichert.<\/p>\n

linkeSeite=solver.Sum([g_i[i] * Variablen[i] for i in range(I)])<\/code><\/p>\n

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

Die Kapazit\u00e4tsrestriktion wird nun an den Solver \u00fcbergeben. Das macht die Funktion Solver.Add.<\/p>\n

solver.Add(linkeSeite<=K)<\/code><\/p>\n

Der Parameter K beinhaltet unseren oben definierten Paramter f\u00fcr die Kapazit\u00e4t (K=7).<\/p>\n

Zielfunktion
\nGanz \u00e4hnlich zur Restriktion wird nun die Zielfunktion als eigenes Objekt ZF definiert.<\/p>\n

ZF=solver.Sum([Variablen[i] * u_i[i] for i in range(I)])<\/code><\/p>\n

Anstelle des Gewichtes werden hier die Nutzwerte (jeweils das ite Element aus der Liste u_i) mit dem zugeh\u00f6rigen Variablenwert von i multipliziert.<\/p>\n

Zuletzt wird die Optimierungsrichtung festgelegt:<\/p>\n

objective=solver.Maximize(ZF)<\/code><\/p>\n

Und schon beauftragen wir den Solver mit der L\u00f6sung des Modells:<\/p>\n

solver.Solve()<\/code><\/p>\n

Hier noch einige Zeilen zur Auswertung der L\u00f6sung. Diese beinhalten Ausgabe des Zielfunktionswertes, der ben\u00f6tigten Rechenzeit, Iterationen und der L\u00f6sung selbst.<\/p>\n

print('Zielfunktionswert:', solver.Objective().Value())
\nprint('WallTime:', solver.WallTime())
\nprint('iterations:', solver.Iterations())
\nprint()<\/p>\n

for i in range(I):
\n print(\"Variablenwert Gegenstand %i: %i\" % (i,Variablen[i].SolutionValue()))<\/p>\n

optimale_Loesung=[]
\nfor i in range(I):
\n if Variablen[i].SolutionValue()==1:
\n  optimale_Loesung.append(Namen_der_Gegenstaende[i])<\/p>\n

print(\"Inhalt des Rucksacks: \",optimale_Loesung )<\/code><\/p>\n

Hier die fertige Python-Datei<\/a> zum Download.<\/p>\n","protected":false},"excerpt":{"rendered":"

Zun\u00e4chst 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\u00e4nkter Kapazit\u00e4t zu packen. Dabei k\u00f6nnen verschieden Gegenst\u00e4nde entweder eingepackt werden, oder zur\u00fcckgelassen werden. F\u00fcr jeden Gegenstand gibt es im Modell eine Bin\u00e4rvariable , die den Wert eins annimmt, wenn der […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[14],"tags":[],"class_list":["post-596","post","type-post","status-publish","format-standard","hentry","category-google-or-tools"],"_links":{"self":[{"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/596","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=596"}],"version-history":[{"count":53,"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/596\/revisions"}],"predecessor-version":[{"id":657,"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/596\/revisions\/657"}],"wp:attachment":[{"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=596"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=596"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=596"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}