LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup

摘要

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 LPDP‐VNS that combines linear programming (LP) relaxation and dynamic programming (DP) to enhance variable neighborhood search (VNS). The LPDP‐VNS is tailored to the characteristics of the MKPS and reduced to LPDP to solve the KPS. The approach is tested on 200 KPS and 360 MKPS benchmark instances. Computational experiments show the effectiveness of the LPDP‐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 LPDP‐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.