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)
DOI: 10.26083/tuprints-00019404,
[Report]

This is the latest version of this item.

[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.

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: 01 Sep 2021 12:15
DOI: 10.26083/tuprints-00019404
URN: urn:nbn:de:tuda-tuprints-194043
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/19404
Export:

Available Versions of this Item

  • A new exact algorithm to solve the Multiple-Choice Multidimensional Knapsack Problem: The Utility Sorted Branch and Bound Algorithm. (deposited 01 Sep 2021 12:14) [Currently Displayed]
Actions (login required)
View Item View Item