Solution Methods for the Multiple-Choice Knapsack Problem and Their Applications

Tibor Szkaliczki ()
Additional contact information
Tibor Szkaliczki: HUN-REN Institute for Computer Science and Control, 1111 Budapest, Hungary

Mathematics, 2025, vol. 13, issue 7, 1-35

Abstract: The Knapsack Problem belongs to the best-studied classical problems in combinatorial optimization. The Multiple-choice Knapsack Problem (MCKP) represents a generalization of the problem, with various application fields such as industry, transportation, telecommunication, national defense, bioinformatics, finance, and life. We found a lack of survey papers on MCKP. This paper overviews MCKP and presents its variants, solution methods, and applications. Traditional operational research methods solving the knapsack problem, such as dynamic programming, greedy heuristics, and branch-and-bound algorithms, can be adapted to MCKP. Only a few algorithms appear to have solved the problem in recent years. We found various related problems during the literature study and explored the broad spectrum of application areas. We intend to inspire research into MCKP algorithms and motivate experts from different domains to apply MCKP.

Keywords: multiple-choice knapsack problem; knapsack problem; greedy heuristics; dynamic programming; combinatorial optimization (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/7/1097/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/7/1097/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:7:p:1097-:d:1621731

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().