An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem

Mhand Hifi (), Slim Sadfi and Abdelkader Sbihi ()
Additional contact information
Mhand Hifi: LaRIA, CERMSEM - CEntre de Recherche en Mathématiques, Statistique et Économie Mathématique - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique
Slim Sadfi: LaRIA, CERMSEM - CEntre de Recherche en Mathématiques, Statistique et Économie Mathématique - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique
Abdelkader Sbihi: CERMSEM - CEntre de Recherche en Mathématiques, Statistique et Économie Mathématique - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

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; optimisation combinatoire; séparation et évaluation; algorithme séquentiel; problème du sac-à-dos (search for similar items in EconPapers)
Date: 2004-03
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-03322716v1
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in 2004

Downloads: (external link)
https://shs.hal.science/halshs-03322716v1/document (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:hal:journl:halshs-03322716

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().