𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Development of core to solve the multidimensional multiple-choice knapsack problem

✍ Scribed by Taha Ghasemi; Mohammadreza Razzazi

Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
426 KB
Volume
60
Category
Article
ISSN
0360-8352

No coin nor oath required. For personal study only.

✦ Synopsis

The multidimensional multiple-choice knapsack problem (MMKP) is an extension of the 0-1 knapsack problem. The core concept has been used to design efficient algorithms for the knapsack problem but the core has not been developed for the MMKP so far. In this paper, we develop an approximate core for the MMKP and utilize it to solve the problem exactly.

Computational results show that the algorithm can solve large uncorrelated instances (up to 100 classes and 100 items in each class) and correlated instances with small number of constraints (up to 5) efficiently. In particular, it solves recently published hard instances for the MMKP in less than a second. The algorithm consumes negligible memory, and compared with the best previous exact algorithm for the MMKP performs significantly faster.

πŸ“œ SIMILAR VOLUMES

Calculating the upper bound of the Multi
Calculating the upper bound of the Multiple-Choice Knapsack Problem
✍ Yuji Nakagawa; Masachika Kitao; Mitsuhiro Tsuji; Yoshinobu Teraoka πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 179 KB

## Abstract An upper bound or a lower bound of the Multiple‐Choice Knapsack Problem can be calculated by solving LP relaxation. In 1979, Sinha and Zoltners proposed a branch‐and‐bound algorithm for solving the Multiple‐Choice Knapsack Problem, and provided a method to obtain the strict upper bound.