Matheuristics for solving the Multiple Knapsack Problem with Setup. (March 2019)

• Record Type: Journal Article
• Authors: Lahyani, Rahma; Chebil, Khalil; Khemakhem, Mahdi; Coelho, Leandro C.
• Is Part Of: Computers & industrial engineering. Volume 129(2019)
• Page Start: 76
• Page End: 89
• Publication Date: 2019-03
• Subjects: Multiple Knapsack Problem with Setup -- Matheuristic -- Tabu search; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.01.010
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We model and solve the multiple knapsack problem with setup. We propose a two-phase and a tabu search embedded matheuristics. We evaluate their performance on a set of instances against 5 different methods. We generate a new testbed for the MKPS and we compare the results to exact solutions. We provide 185 new best known solutions and reach optimality on 93 other instances. 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.