Hybrid algorithms for the Multiple-choice Multi-dimensional Knapsack Problem

Nawal Cherfi and Mhand Hifi

International Journal of Operational Research, 2009, vol. 5, issue 1, 89-109

Abstract: In this paper, we propose three versions of an algorithm for approximately solving large-scale Multiple-choice Multi-dimensional Knapsack Problems (MMKP). First, an adaptation of the local branching is proposed. Second, a hybrid solution procedure is presented that is based on two complementary solution procedures: a local branching which cooperates with a column generation solution procedure. Third and last, an augmented algorithm of the last hybrid algorithm is developed. It can also be viewed as a special truncated branch and bound in which the first hybrid algorithm is applied to a subset of elite nodes generated according to some variables/constraint branchings. The proposed methods are analysed computationally on a set of instances of the literature and compared to the results provided by other algorithms of the literature. Encouraging results have been obtained.

Keywords: branch-and-bound; column generation; heuristics; knapsack problem; local branching; optimisation; multiple choice; hybrid algorithms. (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.inderscience.com/link.php?id=24531 (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:5:y:2009:i:1:p:89-109

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