An exact algorithm for the multiple-choice multidimensional knapsack problem

Mhand Hifi (), Slim Sadfi () and Abdelkader Sbihi ()
Additional contact information
Mhand Hifi: LaRIA et CERMSEM
Slim Sadfi: LaRIA et CERMSEM
Abdelkader Sbihi: CERMSEM

Cahiers de la Maison des Sciences Economiques from Université Panthéon-Sorbonne (Paris 1)

Abstract: In this paper, we propose an optimal algorithm for the Multiple-choice Multidimensional Knapsack Problem MMKP. The main principle of the approach is twofold: (i) to generate an initial solution, and (ii) at different levels of the tree search to determine a new upper bound used with a best-first search strategy. The developed method was able to optimally solve the MMKP. The performance of the exact algorithm is evaluated on a set of small and medium instances. This algorithm is parallelizable and it is one of its important feature

Keywords: Combinatorial optimization; branch and bound; sequential algorithm; Knapsack problem (search for similar items in EconPapers)
JEL-codes: C44 C61 C63 (search for similar items in EconPapers)
Pages: 17 pages
Date: 2004-03
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://halshs.archives-ouvertes.fr/halshs-03322716 (application/pdf)

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:mse:wpsorb:b04024

Access Statistics for this paper

More papers in Cahiers de la Maison des Sciences Economiques from Université Panthéon-Sorbonne (Paris 1) Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().