We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup.
- Authors
Masmoudi, Malek; Adouani, Yassine; Jarboui, Bassem
- 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.
- Subjects
DYNAMIC programming; KNAPSACK problems; LINEAR programming; INTEGER programming; ALGORITHMS
- Publication
International Transactions in Operational Research, 2024, Vol 31, Issue 3, p1890
- ISSN
0969-6016
- Publication type
Article
- DOI
10.1111/itor.13213