An algorithm for the disjunctively constrained knapsack problem

Mhand Hifi and Nabil Otmani

International Journal of Operational Research, 2012, vol. 13, issue 1, 22-43

Abstract: This paper proposes an adaptation of the scatter search (SS) meta-heuristic for approximately solving the disjunctively constrained knapsack problem (DCKP). The DCKP can be viewed as a variant of the standard knapsack problem with special disjunctive constraints. Two versions of SS are presented which are organised following the usual structure of SS. The method is analysed computationally on a set of problem instances of the literature and compared to the results provided by the Cplex solver and other algorithms of the literature. For these instances, most of which cannot be solved to proven optimality in a reasonable time, the proposed method provides results of high quality within reasonable computational time.

Keywords: heuristics; disjunctive constraints; knapsack problem; optimisation; scatter search. (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.inderscience.com/link.php?id=44026 (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:13:y:2012:i:1:p:22-43

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 ().