Titelaufnahme

Titel
Lösungsmethoden für das Multidimensional Multiple-Choice Knapsack Problem / Christian Lorenz
Weitere Titel
Solution methods for the multidimensional multiple-choice knapsack problem
Verfasser/ VerfasserinLorenz, Christian
Begutachter / BegutachterinPferschy Ulrich
Erschienen2012
Umfang41 Bl. : 2 Zsfassungen
HochschulschriftGraz, Univ., Masterarb., 2012
Anmerkung
Zsfassung in dt. und engl. Sprache
Anmerkung
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
SpracheDeutsch
DokumenttypMasterarbeit
Schlagwörter (GND)Rucksackproblem / Rucksackproblem / Online-Publikation
URNurn:nbn:at:at-ubg:1-39201 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Lösungsmethoden für das Multidimensional Multiple-Choice Knapsack Problem [0.57 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Die vorliegende Masterarbeit befasst sich mit dem Multidimensional Multiple-Choice Knapsack Problem (MMKP). Ziel dieser Literaturarbeit ist es, einen Überblick über bestehende Lösungsverfahren zu geben. Das Knapsack Problem ist NP-hard. Es ist also nicht zu erwarten, dass es einen Algorithmus gibt, welcher das Knapsack Problem in polynomieller Laufzeit optimal löst. Abweichend von anderen Knapsack Problemen ist beim MMKP auch das Finden einer zulässigen Lösung nicht trivial. So müssen dafür im ungünstigsten Fall alle möglichen Kombinationen überprüft werden. Da das Lösen dieser Probleme generell sehr aufwändig ist, sind viele der vorhandenen Algorithmen relativ neu. Kapitel zwei gibt eine Einleitung zum Knapsack Problem als solches. Daneben werden verschieden Typen von Knapsack Problemen vorgestellt, die bei Lösungsverfahren für das MMKP Relevanz haben: das 0-1 Knapsack Problem (KP), das Multidimensional Knapsack Problem (MDKP) und das Multiple-Choice Knapsack Problem (MCKP). Kapitel drei legt das Multidimensional Multiple-Choice Knapsack Problem dar. In den Kapiteln zwei und drei wird die Notation eingeführt, wie sie bei der Beschreibung der einzelnen Verfahren zur Anwendung kommt. Kapitel vier untersucht Algorithmen zum exakten Lösen des Multidimensional Multiple-Choice Knapsack Problems. Die drei in der Literatur bekannten Verfahren: der "BBLP"-Algorithmus , der "EMKP"-Algorithmus und ein Core-Konzept werden eingehend untersucht. Alle diese Ansätze basieren auf einem Branch and Bound-Verfahren. Der charakteristische Suchbaum wird allerdings auf unterschiedliche Art aufgebaut.Kapitel fünf behandelt Heuristiken. Einzelne Algorithmen werden dabei ausführlich beschrieben. So werden ein bekannter, auf Lagrange Multiplikatoren basierender Ansatz von Moser et al., ein auf Ant Colony Optimization (ACO) basierender Algorithmus und der "HMMKP"-Algorithmus detailliert dargelegt. Einige andere Algorithmen werden dagegen nur kurz umrissen.

Zusammenfassung (Englisch)

The present master thesis is concerned with the multidimensional multiple-choice knapsack problem (MMKP). The objective of this literature review is to give an overview of existing methods of solution methods. The Knapsack problem is NP-hard. Therefore it's not to be expected, that there is an algorithm that solves the knapsack problem optimally in polynomial time. Unlike other knapsack problems for the multidimensional multiple-choice knapsack problem (MMKP) finding a feasible solution is not trivial. In the worst case, all possible combinations have to be checked. Since solving these problems generally needs a lot of effort, many of the existing algorithms are relatively new. Chapter two gives an introduction to the knapsack problem as such. In addition, different types of knapsack problems are presented which have relevance in solution methods for the MMKP: the 0-1 knapsack problem (KP), the multidimensional knapsack problem (MDKP) and the multiple-choice knapsack problem (MCKP). Chapter three presents the multidimensional multiple-choice knapsack problem (MMKP). In chapters two and three, the notation as used in the description the various methods, is introduced. Chapter four examines algorithms to obtain exact solutions for the multidimensional multiple-choice knapsack problem. The three known in the literature are thoroughly investigated: the "BBLP" algorithm, the "EMKP" algorithm and a core concept. All these approaches are based on a branch and bound method. The typical search tree is built, however, in different ways.Chapter five treats heuristics. Some of the algorithms are described in detail. Thus, a well-known approach based on Lagrange multipliers by Moser et al., an ant colony optimization (ACO)-based algorithm and the "HMMKP" algorithm are presented in detail. Some other algorithms are only briefly outlined.

Statistik
Das PDF-Dokument wurde 171 mal heruntergeladen.