Knapsack problems are among the most intensely studied problems in combinatorial optimization. In this paper, Ykman-Couvreur et al. present “a new fast and lightweight heuristic for finding near-optimal solutions for [multidimension multichoice knapsack problems (MMKPs)].” The MMKP is a combination of the multidimension knapsack problem (where several resources are present, but only one set) and the multichoice knapsack problem (where several sets exist, but only one resource). Within this framework, the authors introduce a multiprocessor system-on-chip (MP-SoC) heuristic suitable for multiprocessor platforms, which they then challenge on both solution quality and performance, compared with the state-of-the-art heuristics.
Although the discussed issue is very complex, the authors manage to find an optimal balance between a comprehensive presentation, in terms of a consistent thread and useful illustrations, and high mathematical accuracy. However, while this paper targets specialists in this area with an interest in efficient algorithms for solving MMKPs, it fails to attract mathematicians in other disciplines.
Based on the remarkable advantages of the presented study, the paper is recommended to readers with further applications in mind.