TU Darmstadt / ULB / TUprints

A new exact algorithm to solve the Multiple-Choice Multidimensional Knapsack Problem: The Utility Sorted Branch and Bound Algorithm

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. (Publisher's Version)
Darmstadt, DOI: 10.26083/tuprints-00019404,
[Report]

[img]
Preview
Text
Kreß et al. (2021) A new exact algorithm to solve the Multiple-Choice Multidimensional Knapsack Problem.pdf
Available under: CC BY 4.0 International - Creative Commons, Attribution.

Download (367kB) | Preview
Item Type: Report
Status: Publisher's Version
Title: A new exact algorithm to solve the Multiple-Choice Multidimensional Knapsack Problem: The Utility Sorted Branch and Bound Algorithm
Language: English
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.

Place of Publication: Darmstadt
Classification DDC: 500 Naturwissenschaften und Mathematik > 510 Mathematik
600 Technik, Medizin, angewandte Wissenschaften > 620 Ingenieurwissenschaften
Divisions: 16 Department of Mechanical Engineering > Institute of Production Technology and Machine Tools (PTW)
16 Department of Mechanical Engineering > Institute of Production Technology and Machine Tools (PTW) > CiP Center for industrial Productivity
Date Deposited: 01 Sep 2021 12:14
Last Modified: 22 Sep 2022 07:51
DOI: 10.26083/tuprints-00019404
URN: urn:nbn:de:tuda-tuprints-194043
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/19404
PPN: 486168034
Export:
Actions (login required)
View Item View Item