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,"
Documents de Travail de l'OFCE
2011-04, Observatoire Francais des Conjonctures Economiques (OFCE).
- 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.
- 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 you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.