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

    5 Citations (Scopus)

    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

    Keywords

    • knapsack problem
    • modelling
    • multiple-choice multidimensional knapsack problem
    • reformulation
    • set partitioning problem

    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