A set partitioning reformulation for the multiple-choice multidimensional knapsack problem

Stefan Voß*, Eduardo Lalla-Ruiz

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

11 Citations (Scopus)
73 Downloads (Pure)

Abstract

The Multiple-choice Multidimensional Knapsack Problem (MMKP) is a well-known -hard combinatorial optimization problem that has received a lot of attention from the research community as it can be easily translated to several real-world problems arising in areas such as allocating resources, reliability engineering, cognitive radio networks, cloud computing, etc. In this regard, an exact model that is able to provide high-quality feasible solutions for solving it or being partially included in algorithmic schemes is desirable. The MMKP basically consists of finding a subset of objects that maximizes the total profit while observing some capacity restrictions. In this article a reformulation of the MMKP as a set partitioning problem is proposed to allow for new insights into modelling the MMKP. The computational experimentation provides new insights into the problem itself and shows that the new model is able to improve on the best of the known results for some of the most common benchmark instances.

Original languageEnglish
Pages (from-to)831-850
Number of pages20
JournalEngineering Optimization
Volume48
Issue number5
DOIs
Publication statusPublished - 3 May 2016
Externally publishedYes

Keywords

  • Knapsack problem
  • Modelling
  • Multiple-choice multidimensional knapsack problem
  • Reformulations
  • Set partitioning problem
  • 2023 OA procedure

Fingerprint

Dive into the research topics of 'A set partitioning reformulation for the multiple-choice multidimensional knapsack problem'. Together they form a unique fingerprint.

Cite this