Title: Heuristics for the multiple knapsack problem with conflicts

Authors: Chuda Basnet

Addresses: Department of Management Systems, Waikato Management School, The University of Waikato, Private Bag 3105, Hamilton 3216, New Zealand

Abstract: In this paper we discuss a variant of the 0-1 knapsack problem, where there are multiple knapsacks to fill with items that have profits and sizes associated with them. The objective is to maximise the profit by selecting items to fill the knapsacks within their space constraints. In the version of the problem considered in this paper, some of the items are incompatible with each other, and cannot be placed together in the same knapsack. We apply some newly developed heuristics to the problem and compare the results with those found by a commercial optimisation package. Computational results are presented. The contributions of this paper are an upper bound, and the heuristics developed and tested in this paper.

Keywords: multiple knapsack; graph colouring; heuristic algorithms; incompatibility constraints.

DOI: 10.1504/IJOR.2018.093509

International Journal of Operational Research, 2018 Vol.32 No.4, pp.514 - 525

Received: 12 Nov 2015
Accepted: 28 Oct 2016
Published online: 27 Jul 2018 *

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