An exact algorithm for the multiple-choice multidimensional knapsack problem
AbstractIn 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.
Download InfoTo our knowledge, this item is not available for download. To find whether it is available, there are three options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page whether it is in fact available.
3. Perform a search for a similarly titled item that would be available.
Bibliographic InfoPaper provided by Université Panthéon-Sorbonne (Paris 1) in its series Cahiers de la Maison des Sciences Economiques with number b04024.
Length: 16 pages
Date of creation: Mar 2004
Date of revision:
Contact details of provider:
Postal: 106 - 112 boulevard de l'Hôpital, 75647 Paris cedex 13
Phone: 01 44 07 81 00
Fax: 01 44 07 81 09
Web page: http://mse.univ-paris1.fr/
More information through EDIRC
Combinatorial optimization; branch and bound; sequential algorithm; Knapsack problem.;
Find related papers by JEL classification:
- C44 - Mathematical and Quantitative Methods - - Econometric and Statistical Methods: Special Topics - - - Operations Research; Statistical Decision Theory
- C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis
- C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
This paper has been announced in the following NEP Reports:
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Sylvain Barde, 2011.
"Ignorance is bliss: rationality, information and equilibrium,"
Studies in Economics
1103, Department of Economics, University of Kent.
- Sylvain Barde, 2011. "Ignorance is bliss: rationality, information and equilibrium," Sciences Po publications 2011-04, Sciences Po.
- Sylvain Barde, 2011. "Ignorance is bliss: rationality, information and equilibrium," Documents de Travail de l'OFCE 2011-04, Observatoire Francais des Conjonctures Economiques (OFCE).
- N. Cherfi & M. Hifi, 2010. "A column generation method for the multiple-choice multi-dimensional knapsack problem," Computational Optimization and Applications, Springer, vol. 46(1), pages 51-73, May.
- Sylvain Barde, 2012. "Back to the future: economic rationality and maximum entropy prediction," Studies in Economics 1202, Department of Economics, University of Kent.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Lucie Label).
If references are entirely missing, you can add them using this form.