- Journal
- INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
- Année
- 2024
- Volume
- 31
- Numéro
- 3
- Pages
- 1890-1916
- Mois
- MAY
- DOI
- 10.1111/itor.13213
Abstract
We consider the multiple knapsack problem (KP) with setup (MKPS), which is an extension of the KP with setup (KPS). We propose a new solving approach denoted by LP&DP-VNS that combines linear programming (LP) relaxation and dynamic programming (DP) to enhance variable neighborhood search (VNS). The LP&DP-VNS is tailored to the characteristics of the MKPS and reduced to LP&DP to solve the KPS. The approach is tested on 200 KPS and 360 MKPS benchmark instances. Computational experiments show the effectiveness of the LP&DP-VNS, compared to integer programming (using CPLEX) and the best state-of-the-art algorithms. It reaches 299/342 optimal solutions and 316/318 best-known solutions and provides 127 new best solutions. An additional computational study shows that the LP&DP-VNS scales up extremely well, solving optimally and near-optimally very large instances with up 200 families and 300,000 items in a reasonable amount of time.