A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem

Abdelkader Sbihi ()
Additional contact information
Abdelkader Sbihi: Lancaster University Management School, Optimisation Research Centre

Journal of Combinatorial Optimization, 2007, vol. 13, issue 4, No 3, 337-351

Abstract: 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 feasible solution as a starting lower bound, and (ii) at different levels of the search tree to determine an intermediate upper bound obtained by solving an auxiliary problem called MMKPaux and perform the strategy of fixing items during the exploration. The approach which we develop is of best-first search strategy. The method was able to optimally solve the MMKP. The performance of the exact algorithm is evaluated on a set of small and medium instances, some of them are extracted from the literature and others are randomly generated. This algorithm is parallelizable and it is one of its important feature.

Keywords: Combinatorial optimization; Branch and bound; Sequential algorithm; Knapsack (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-9035-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:13:y:2007:i:4:d:10.1007_s10878-006-9035-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-006-9035-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().