Heuristic algorithms for the multiple-choice multidimensional knapsack problem

M Hifi (), M Michrafy and A Sbihi ()
Additional contact information
M Hifi: LaRIA, UPJV
M Michrafy: CERMSEM-CNRS UMR 8095, Universite de Paris 1
A Sbihi: LaRIA, UPJV

Journal of the Operational Research Society, 2004, vol. 55, issue 12, 1323-1332

Abstract: Abstract In this paper, we propose several heuristics for approximately solving the multiple-choice multidimensional knapsack problem (noted MMKP), an NP-Hard combinatorial optimization problem. The first algorithm is a constructive approach used especially for constructing an initial feasible solution for the problem. The second approach is applied in order to improve the quality of the initial solution. Finally, we introduce the main algorithm, which starts by applying the first approach and tries to produce a better solution to the MMKP. The last approach can be viewed as a two-stage procedure: (i) the first stage is applied in order to penalize a chosen feasible solution and, (ii) the second stage is used in order to normalize and to improve the solution given by the firs stage. The performance of the proposed approaches has been evaluated based problem instances extracted from the literature. Encouraging results have been obtained.

Keywords: combinatorial optimization; guided local search; heuristic; knapsack (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601796 Abstract (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:pal:jorsoc:v:55:y:2004:i:12:d:10.1057_palgrave.jors.2601796

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601796

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().