Advanced Search
MyIDEAS: Login

An exact algorithm for the multiple-choice multidimensional knapsack problem

Contents:

Author Info

  • Mhand Hifi

    () (LaRIA et CERMSEM)

  • Slim Sadfi

    () (LaRIA et CERMSEM)

  • Abdelkader Sbihi

    () (CERMSEM)

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.

Download Info

To 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 Info

Paper provided by Université Panthéon-Sorbonne (Paris 1) in its series Cahiers de la Maison des Sciences Economiques with number b04024.

as in new window
Length: 16 pages
Date of creation: Mar 2004
Date of revision:
Handle: RePEc:mse:wpsorb:b04024

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
Email:
Web page: http://mse.univ-paris1.fr/
More information through EDIRC

Related research

Keywords: Combinatorial optimization; branch and bound; sequential algorithm; Knapsack problem.;

Find related papers by JEL classification:

This paper has been announced in the following NEP Reports:

References

No references listed on IDEAS
You can help add them by filling out this form.

Citations

Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
as in new window

Cited by:
  1. Sylvain Barde, 2012. "Back to the future: economic rationality and maximum entropy prediction," Studies in Economics 1202, Department of Economics, University of Kent.
  2. 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.

Lists

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

Statistics

Access and download statistics

Corrections

When requesting a correction, please mention this item's handle: RePEc:mse:wpsorb:b04024

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.