Beitrag teilen
6 Min. Lesezeit
20. Oktober 2017, aktualisiert am 13.01.2022 · Dr. Florian Diedrich
20. Oktober 2017, aktualisiert am 13.01.2022 · Dr. Florian Diedrich
I
mmer wenn irgendwo etwas quantifiziert wird und auf bestehenden Daten eine Entscheidung getroffen werden soll, ist irgendwo ein Optimierungsproblem aufgetreten. Da dieses dann oft wiederholt mit jeweils verschiedenen Daten gelöst werden muss, stellt sich natürlich die Frage nach einem Algorithmus. Man möchte dann auch wissen, wie gut dieser zur Lösung des Problems geeignet ist.
In diesem Artikel stellen wir ein grundlegendes Optimierungsproblem vor: das Rucksackproblem. Zuerst definieren wir kurz das Problem und nehmen ein paar Eigenschaften zur Kenntnis. Dann stellen wir einen naheliegenden Algorithmus zur Lösung dar.
Achtung: Trotz seines intuitiven Charakters kann der Algorithmus aber nicht nur suboptimale, sondern überraschenderweise sogar beliebig schlechte Lösungen liefern!
Schließlich stellen wir eine einfache Verbesserung dieses Algorithmus vor, die eine beweisbare Gütegarantie hat und somit ein Approximationsalgorithmus1 ist.
In diesem Artikel stellen wir ein grundlegendes Optimierungsproblem vor: das Rucksackproblem. Zuerst definieren wir kurz das Problem und nehmen ein paar Eigenschaften zur Kenntnis. Dann stellen wir einen naheliegenden Algorithmus zur Lösung dar.
Achtung: Trotz seines intuitiven Charakters kann der Algorithmus aber nicht nur suboptimale, sondern überraschenderweise sogar beliebig schlechte Lösungen liefern!
Schließlich stellen wir eine einfache Verbesserung dieses Algorithmus vor, die eine beweisbare Gütegarantie hat und somit ein Approximationsalgorithmus1 ist.
DAS RUCKSACKPROBLEM: EINFÜHRUNG
Beim Rucksackproblem2 sind eine Menge von n Items („Gegenstände“) und ein Rucksack vorgegeben. Dabei hat jedes Item sowohl ein Gewicht als auch einen Profit und der Rucksack hat eine vorgegebene Kapazität; alle diese Werte sind positiv und ganzzahlig.
Das Ziel ist, eine Auswahl von Items zu finden, die zulässig ist (d.h. die Summe ihrer Gewichte übersteigt die Kapazität des Rucksacks nicht) und einen maximalen Gesamtprofit hat (d.h. die Summe der Profite ist so groß wie möglich). Ein konkreter Datensatz des Problems wird als Instanz bezeichnet.
Instanz:
- Item 1: Gewicht 188, Profit 635
- Item 2: Gewicht 250, Profit 108
- Item 3: Gewicht 2100, Profit 545
- Rucksack mit Kapazität 2500
Eine optimale Lösung besteht dabei aus den Items 1 und 3 und hat den Profit 1180.
Ein Bezug zum Field Service Management und zur Logistik ist klar vorhanden, da dort beispielsweise ein Transportfahrzeug unter Berücksichtigung seiner Kapazität profitmaximierend mit Gütern beladen werden soll.
Obwohl dieses Beispiel die Auswahl von physischen Objekten behandelt, kann man ebenso das Gewicht als Zeit interpretieren; statt des Rucksacks steht dann zu verplanende Arbeitszeit zur Verfügung, wobei die Items zur Auswahl stehende Aufträge sind, deren Profit ein zu erwartender wirtschaftlicher Nutzen ist. Ferner kann das Rucksackproblem auch als Teilproblem in komplexeren Optimierungsszenarien auftreten.
Rucksäcke gibt es schon sehr lange. Ebenso alt ist das Problem, sie sinnvoll zu packen. Quelle: FLS GmbH
Es ist einsichtig, dass man eine optimale Lösung erhalten kann, indem man alle Auswahlmöglichkeiten erzeugt, auf Zulässigkeit überprüft und die Gesamtprofite aller zulässigen Lösungen vergleicht. Da allerdings für n Items die Anzahl der Teilmengen 2n ist, wächst die Anzahl der zu betrachtenden potenziellen Lösungen stark in der Anzahl der Items an; dieses Vorgehen ist als nicht praktikabel3 anzusehen. Da das Rucksackproblem gleichzeitig NP-schwer4 ist, ist die Existenz eines wesentlich besseren exakten Lösungsalgorithmus eher unwahrscheinlich.
In jedem Fall kann aber die Instanz ausgeschöpft werden, d.h. wir modifizieren die Eingabe so, dass relativ uninteressante Randfälle ausgeschlossen werden, das Optimum jedoch nicht verändert wird. Wenn ein Item größeres Gewicht hat als die Kapazität des Rucksacks, kann es in keiner Lösung vorkommen und wird entfernt. Weiter kann geprüft werden, ob alle Items zusammen in den Rucksack passen; falls ja, ist ebenfalls eine optimale Lösung gefunden5.
EIN GREEDY-ANSATZ
Eine naheliegende Idee ist, die Items nach ihrer Effizienz zu bewerten und auszuwählen; intuitiv soll dadurch die zur Verfügung stehende Kapazität möglichst gut ausgenutzt werden. Für jedes Item wird also seine Effizienz (das ist der Quotient aus Profit und Gewicht) berechnet. Dann werden die Items in absteigender6 Reihenfolge ihrer Effizienz in den Rucksack gepackt, bis kein Item mehr passt.
Diese Heuristik wird als greedy („gierig“) bezeichnet, da sie versucht, jeweils bestmögliche Einzelschritte auszuwählen, aber getroffene Entscheidungen nicht revidieren kann.
Dieser Algorithmus ist wesentlich schneller als die Bewertung aller potenziellen Lösungen; allerdings erzeugt sie nicht nur nicht immer eine optimale Lösung, sondern sie kann verglichen mit dem jeweiligen Optimum sogar beliebig schlecht sein! Dies kann man überraschenderweise an einer an k parametrisierten Menge von Instanzen mit nur 2 Items erkennen.
Instanz:
- Item 1: Gewicht 1, Profit 1 („schlechtes Item“)
- Item 2: Gewicht k, Profit k-1 („gutes Item“)
- Rucksack mit Kapazität k
Da die Kapazität k ist, die Summe der Gewichte aber k+1, passen nicht beide Items in den Rucksack. Da beide Items alleine aber in den Rucksack passen, kommen nur 2 Lösungen in Frage.
Weil Item 2 einen größeren Profit hat als Item 1, ist Item 2 die optimale Wahl. Allerdings hat Item 1 eine Effizienz von (k-1)/k, was kleiner als 1 ist; da Item 1 die Effizienz 1/1=1 hat, würde durch die oben erwähnte Heuristik die Wahl auf Item 1 fallen. Weil dies nicht optimal ist, wir aber den optimalen Profit kennen, können wir ausrechnen, welchen Anteil am Optimum unsere Heuristik sichergestellt hätte - nämlich den Quotienten aus dem Profit von Item 1 und Item 2. Da dieser 1/(k-1) ist, können wir durch eine geeignete Wahl von k die Lösung unserer Heuristik (verglichen mit dem jeweiligen Optimum) beliebig schlecht werden lassen.
EIN APPROXIMATIONSALGORITHMUS
Hat unsere Intuition uns etwa getäuscht? Das Auswählen der Items nach Effizienz kann doch nicht völlig falsch sein.
Nun, das ist es auch nicht. Der Greedy-Ansatz würde optimale Lösungen berechnen, wenn alle Items die gleiche Größe (z. B. 1) hätten, weil dann jede zur Verfügung stehende Einheit der Kapazität optimal ausgenutzt wäre; Entweder ist der Rucksack dann immer komplett gefüllt oder die restliche Kapazität kann auch durch gar kein Item genutzt werden.
Wir stellen uns vor, dass wir unsere Items in Stücke der Größe 1 zerschneiden, deren Profit jeweils anteilig aus dem Original-Item hervorgeht; somit haben alle diese kleinen Items die gleiche Effizienz wie das Item, aus dem sie entstanden sind und in der Summe auch den Originalprofit. Aus jeder zulässigen Lösung der Originalinstanz wird durch Zerschneiden der Items eine Lösung der zerschnittenen Instanz; da wir also die Lösungsmenge vergrößert haben7, ist das Optimum P2 der zerschnittenen Instanz höchstens größer als das Optimum P1 der Originalinstanz.
Weitere Artikel:
➡ TOPOLOGISCHE SORTIERUNG
➡ TRAVELING SALESPERSON PROBLEM
➡ DYNAMISCHE PROGRAMMIERUNG
➡ GANTT CHARTS IN DER TOURENPLANUNG
In der Sortierung unterstellen wir, dass wir bei der Auswahl der kleinen Stücke nicht zwischen verschiedenen Original-Items hin- und herspringen. Führen wir dann unseren Greedy-Algorithmus aus, wählen wir also zuerst die einzelnen Stücke ganzer Items; das letzte Item passt dann möglicherweise nicht mehr komplett in den Rucksack. Den Rest dieses Items (nennen wir seinen Index j) heben wir auf. Da unser Rucksack keine freie Kapazität mehr hat und jede Kapazitätseinheit optimal ausgenutzt ist, ist sein Gesamtprofit das Optimum P2 der zerschnittenen Instanz.
Leider ist die erzeugte Lösung nicht zulässig für die Originalinstanz, weil das letzte Item j ja zerschnitten wurde. Die ausgewählten nicht zerschnittenen Items passen zusammen in den Rucksack; nehmen wir Item j komplett dazu, haben wir eine Menge von Items, die zwar zusammen nicht mehr in den Rucksack passt, deren Gesamtprofit aber insgesamt mindestens das Optimum der Originalinstanz ist!
Wir vergleichen nun den Profit von Item j und den Gesamtprofit der ausgewählten nicht zerschnittenen Items und nehmen die bessere der beiden Lösungen. Da die Summe dieser Profite mindestens das Optimum der Originalinstanz ist, haben wir somit durch einen effizienten Algorithmus beweisbar mindestens die Hälfte des optimalen Profits gesichert.
Die Gütegarantie von Algorithmen wird üblicherweise so angegeben, dass sie nicht kleiner als 1 ist (ggf. wird zum Kehrwert übergegangen). Unser modifizierter Greedy-Algorithmus ist somit ein Approximationsalgorithmus mit Gütegarantie 2.
Es ist weiter eine naheliegende Frage, ob der oben vorgestellte Approximationsalgorithmus nicht eine bessere Gütegarantie als 2 hat; vielleicht haben wir ja nur dafür keine passenden Argumente gefunden? Leider ist das aber nicht der Fall, wie man an der folgenden, an k parametrisierten Menge von Instanzen mit jeweils 3 Items sieht.
Instanz:
- Item 1: Gewicht 1, Profit 2
- Item 2: Gewicht k, Profit k
- Item 3: Gewicht k, Profit k
- Rucksack mit Kapazität 2k
Der optimale Profit ist 2k durch Auswahl von Item 2 und Item 3. Der Approximationsalgorithmus erreicht durch die Auswahl von Item 1 und Item 2 (oder 3) allerdings nur einen Profit von 2+k. Somit ist also für diese Menge von Instanzen der Anteil des algorithmisch generierten Profits am optimalen Profit immer mindestens (2+k)/(2k)=1/k+1/2. Da sich dieser Quotient für größer werdende Werte von k an 1/2 annähert, ist die Gütegarantie von 2 für unseren Algorithmus exakt.
AUSBLICK
Obwohl das Rucksackproblem selbst relativ einfach zu verstehen ist, gibt es erstaunlich umfangreiche Literatur8, in der für die oben vorgestellte Version und andere Formulierungen Ergebnisse aus verschiedenen Bereichen (exakte Algorithmen, Approximationsalgorithmen, Heuristiken) vorgestellt werden. Natürlich sind die hier vorgestellten Inhalte ebenfalls dort zu finden.
Karriere & Jobs:
Du bist Student*in oder Absolvent*in und interessierst dich für logistische Problemstellungen oder für die Softwareentwicklung? Dann warten bei FLS spannende Aufgaben auf dich. Schau dich auf unserem Karriereportal nach aktuellen Stellenangeboten um oder bewirb dich einfach initiativ:
Anmerkungen:
Vijay Vazirani: Approximation Algorithms, Springer, 2003; Klaus Jansen & Marian Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.
Robert Sedgewick: Algorithmen, Addison-Wesley, 1991.
Für 32 Items sind das über 4 Milliarden Teilmengen; falls ein Mensch pro Sekunde eine Teilmenge bewerten könnte, wäre er damit mehr als 135 schlaflose Jahre beschäftigt.
Michael R. Garey & David S. Johnson: Computers and Intractability – A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
Das ist insbesondere dann so, wenn nach Ausführung der erwähnten Schritte gar kein Item mehr vorhanden ist. Der optimale Zielfunktionswert ist dann 0.
Es ist „monoton fallend“ gemeint.
Die Ersetzung von diskreten Nebenbedingungen (ein Item wird entweder komplett oder gar nicht ausgewählt) durch kontinuierliche Nebenbedingungen (ein Item wird anteilig ausgewählt) wird als Relaxierung bezeichnet; dadurch wird zu einer Obermenge der zulässigen Lösungen übergegangen. Die Zielfunktion bleibt im Wesentlichen gleich; durch den Übergang zu einer Obermenge kann aber das Optimum der Instanz größer werden, weil die Zielfunktion maximiert werden soll.
Silvano Martello & Paolo Toth: Knapsack Problems, John Wiley & Sons, 1990; Hans Kellerer, Ulrich Pferschy & David Pisinger: Knapsack Problems, Springer, 2004; Eugene Lawler: Fast Approximation Algorithms for Knapsack Problems, Mathematics of Operations Research 4(4), 1979.
Vijay Vazirani: Approximation Algorithms, Springer, 2003; Klaus Jansen & Marian Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.
Robert Sedgewick: Algorithmen, Addison-Wesley, 1991.
Für 32 Items sind das über 4 Milliarden Teilmengen; falls ein Mensch pro Sekunde eine Teilmenge bewerten könnte, wäre er damit mehr als 135 schlaflose Jahre beschäftigt.
Michael R. Garey & David S. Johnson: Computers and Intractability – A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
Das ist insbesondere dann so, wenn nach Ausführung der erwähnten Schritte gar kein Item mehr vorhanden ist. Der optimale Zielfunktionswert ist dann 0.
Es ist „monoton fallend“ gemeint.
Die Ersetzung von diskreten Nebenbedingungen (ein Item wird entweder komplett oder gar nicht ausgewählt) durch kontinuierliche Nebenbedingungen (ein Item wird anteilig ausgewählt) wird als Relaxierung bezeichnet; dadurch wird zu einer Obermenge der zulässigen Lösungen übergegangen. Die Zielfunktion bleibt im Wesentlichen gleich; durch den Übergang zu einer Obermenge kann aber das Optimum der Instanz größer werden, weil die Zielfunktion maximiert werden soll.
Silvano Martello & Paolo Toth: Knapsack Problems, John Wiley & Sons, 1990; Hans Kellerer, Ulrich Pferschy & David Pisinger: Knapsack Problems, Springer, 2004; Eugene Lawler: Fast Approximation Algorithms for Knapsack Problems, Mathematics of Operations Research 4(4), 1979.
