Title: Efficient matheuristic for the generalised multiple knapsack problem with setup

Authors: Yassine Adouani; Bassem Jarboui; Malek Masmoudi

Addresses: Laboratory of Modeling and Optimization for Decisional, Industrial and Logistic Systems Laboratory, Faculty of Economics and Management Sciences, University of Sfax, Sfax, Tunisia ' Higher Colleges of Technology, Abu Dhabi, UAE ' Faculty of Sciences and Techniques, University of Lyon, University Jean Monnet Saint-Etienne, 42000 Saint-Etienne, France

Abstract: This paper introduces a new variant of the knapsack problem with setup (KPS). We refer to it as the generalised multiple knapsack problem with setup (GMKPS). GMKPS originates from industrial production problems where the items are divided into classes and processed in multiple periods. We refer to the particular case where items from the same class cannot be processed in more than one period as the multiple knapsack problem with setup (MKPS). First, we provide mathematical formulations of GMKPS and MKPS and provide an upper bound expression for the knapsack problem. We then propose a matheuristic that combines variable neighbourhood descent (VND) with integer programming (IP). We consider local search techniques to assign classes to knapsacks and apply the IP to select the items in each knapsack. Computational experiments on randomly generated instances show the efficiency of our matheuristic in comparison to the direct use of a commercial solver. [Received: 4 March 2018; Revised: 1 June 2019; Revised: 12 July 2019; Revised: 22 November 2019; Accepted: 6 January 2020]

Keywords: knapsack problems; setup; matheuristic; variable neighbourhood descent; VND; integer programming.

DOI: 10.1504/EJIE.2020.109906

European Journal of Industrial Engineering, 2020 Vol.14 No.5, pp.715 - 741

Published online: 29 Sep 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article