Iterative integer linear programming-based heuristic for solving the multiple-choice knapsack problem with setups

This paper studies the multiple-choice knapsack problem with setup (MCKS) which is a generalization of the knapsack problem with setup (KPS) where the items can be processed in multiple periods. The Integer Linear Programming (ILP) of the MCKS shows its limitations when solved using CPLEX 12.7 solver, and the existing algorithms VNS&IP and VND-LB from the literature outperform the ILP and provide the best-known solutions but solve to optimality only 29 out of 120 instances, respectively. This paper is dedicated to exposing an Iterative Integer linear programming-based heuristic (IILP-H) that deals with the MCKS. The IILP-H has been experimented on the MCKS benchmark instances. A sensitivity analysis of the MCKS parameters is provided. A comparison of the IILP-H with the upper bound obtained by the CPLEX 12.7 solver and the best state-of-the-art algorithms has been conducted. The numerical results show that the IILP-H outperforms all the existing solving techniques when it comes to solution quality and computation time. It reaches 120 out of 120 best solutions, including 77 out of 120 optimal and 69 new best solutions. The complexity of the MCKS and the nature of the solutions obtained by the IILP-H are studied regarding the number of periods to which a family is assigned.