Kreß, Antonio ; Kiel, Florian ; Metternich, Joachim (2021)
A new exact algorithm to solve the Multiple-Choice Multidimensional Knapsack Problem:
The Utility Sorted Branch and Bound Algorithm.
doi: 10.26083/tuprints-00019404
Report, Erstveröffentlichung, Verlagsversion
Kurzbeschreibung (Abstract)
This paper offers an exact algorithm for one of the most complex members of the Knapsack Problem family: The Multiple-choice Multidimensional Knapsack Problem (MMKP). Based on a literature survey, only a few exact algorithms exist for the MMKP. The proposed algorithm excludes ranges of the possible solution space through systematic variations of ranked elements by utility sorting. Based on logical rules, successor nodes of a feasible node cannot include the optimal solution. Besides a literature survey as well as a detailed description of the algorithm and the test design, the results of a computational study on 11,160 instances are presented. The efficiency of the algorithm depends on the number of classes, elements per class, number of restrictions, and the degree of restrictiveness. Using the distribution of a search quotient shows the relative number of examined solutions being investigated. Testing against a brute-force algorithm reveals that all problem instances could be solved exactly while reducing the number of node enumerations. Furthermore, the structure of the algorithm allows its usage on other members of the knapsack problem family.
| Typ des Eintrags: | Report |
|---|---|
| Erschienen: | 2021 |
| Autor(en): | Kreß, Antonio ; Kiel, Florian ; Metternich, Joachim |
| Art des Eintrags: | Erstveröffentlichung |
| Titel: | A new exact algorithm to solve the Multiple-Choice Multidimensional Knapsack Problem: The Utility Sorted Branch and Bound Algorithm |
| Sprache: | Englisch |
| Publikationsjahr: | 2021 |
| DOI: | 10.26083/tuprints-00019404 |
| URL / URN: | https://tuprints.ulb.tu-darmstadt.de/19404 |
| Kurzbeschreibung (Abstract): | This paper offers an exact algorithm for one of the most complex members of the Knapsack Problem family: The Multiple-choice Multidimensional Knapsack Problem (MMKP). Based on a literature survey, only a few exact algorithms exist for the MMKP. The proposed algorithm excludes ranges of the possible solution space through systematic variations of ranked elements by utility sorting. Based on logical rules, successor nodes of a feasible node cannot include the optimal solution. Besides a literature survey as well as a detailed description of the algorithm and the test design, the results of a computational study on 11,160 instances are presented. The efficiency of the algorithm depends on the number of classes, elements per class, number of restrictions, and the degree of restrictiveness. Using the distribution of a search quotient shows the relative number of examined solutions being investigated. Testing against a brute-force algorithm reveals that all problem instances could be solved exactly while reducing the number of node enumerations. Furthermore, the structure of the algorithm allows its usage on other members of the knapsack problem family. |
| Status: | Verlagsversion |
| URN: | urn:nbn:de:tuda-tuprints-194043 |
| Sachgruppe der Dewey Dezimalklassifikatin (DDC): | 500 Naturwissenschaften und Mathematik > 510 Mathematik 600 Technik, Medizin, angewandte Wissenschaften > 620 Ingenieurwissenschaften und Maschinenbau |
| Fachbereich(e)/-gebiet(e): | 16 Fachbereich Maschinenbau 16 Fachbereich Maschinenbau > Institut für Produktionsmanagement und Werkzeugmaschinen (PTW) 16 Fachbereich Maschinenbau > Institut für Produktionsmanagement und Werkzeugmaschinen (PTW) > CiP Center für industrielle Produktivität |
| Hinterlegungsdatum: | 01 Sep 2021 12:14 |
| Letzte Änderung: | 07 Sep 2021 05:15 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum