Heuristics for the multiple knapsack problem with conflicts

Chuda Basnet

International Journal of Operational Research, 2018, vol. 32, issue 4, 514-525

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

Downloads: (external link)
http://www.inderscience.com/link.php?id=93509 (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:ijores:v:32:y:2018:i:4:p:514-525

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().