Matheuristics for solving the Multiple Knapsack Problem with Setup

Abstract The knapsack problem is one of the most investigated and applicable combinatorial optimization problems. In this paper we consider a generalized problem called the Multiple Knapsack Problem with Setup (MKPS) in which a set of families of items and a set of knapsacks are available. Each item is characterized by a knapsack-dependent profit and each family is associated with a knapsack-dependent cost. We formally present a mixed-integer linear program of the MKPS and we propose a multi-level matheuristic to solve large size instances of the problem. The matheuristic takes advantage of the structure of the problem and the decomposition principle. Furthermore, we enhance our solution approach combining it with tabu search. We carry out a computational study to assess the performance of the proposed matheuristics on a set of instances from the Knapsack Problem with Setup (KPS) literature. The computational results show that the proposed matheuristic is competitive compared with the state-of-the-art methods. To better evaluate its performance, we generate a new testbed for the MKPS and we compare the results to exact solutions provided by a commercial solver. Computational experiments substantiate the good performance of the proposed methods as they provide new best known values for 185 instances out of 360 in a very competitive running time.