Efficient matheuristic for the generalised multiple knapsack problem with setup

Yassine Adouani, Bassem Jarboui and Malek Masmoudi

European Journal of Industrial Engineering, 2020, vol. 14, issue 5, 715-741

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. (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=109906 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:eujine:v:14:y:2020:i:5:p:715-741

Access Statistics for this article

More articles in European Journal of Industrial Engineering from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().