A set partitioning reformulation for the multiple-choice multidimensional knapsack problem. Issue 5 (3rd May 2016)

• Record Type: Journal Article
• Authors: Voß, Stefan; Lalla-Ruiz, Eduardo
• Is Part Of: Engineering optimization. Volume 48:Issue 5(2016)
• Page Start: 831
• Page End: 850
• Publication Date: 2016-05-03
• Subjects: knapsack problem -- reformulation -- modelling -- set partitioning problem -- multiple-choice multidimensional knapsack problem; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2015.1062094
• Languages: English
• ISSNs: 0305-215X

Abstract

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.