IDEAS home Printed from https://ideas.repec.org/p/hal/journl/halshs-03322716.html
   My bibliography  Save this paper

An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem

Author

Listed:
  • Mhand Hifi

    (LaRIA, CERMSEM - CEntre de Recherche en Mathématiques, Statistique et Économie Mathématique - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique)

  • Slim Sadfi

    (LaRIA, CERMSEM - CEntre de Recherche en Mathématiques, Statistique et Économie Mathématique - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique)

  • Abdelkader Sbihi

    (CERMSEM - CEntre de Recherche en Mathématiques, Statistique et Économie Mathématique - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique)

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.

Suggested Citation

  • Mhand Hifi & Slim Sadfi & Abdelkader Sbihi, 2004. "An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem," Post-Print halshs-03322716, HAL.
    • Handle: RePEc:hal:journl:halshs-03322716
    Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-03322716
    as

    Download full text from publisher

    File URL: https://shs.hal.science/halshs-03322716/document
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Luss, Hanan, 1992. "Minimax resource allocation problems: Optimization and parametric analysis," European Journal of Operational Research, Elsevier, vol. 60(1), pages 76-86, July.
    2. Pang, Jong-Shi & Chang-Sung, Yu, 1989. "A min-max resource allocation problem with substitutions," European Journal of Operational Research, Elsevier, vol. 41(2), pages 218-223, July.
    3. Yoshiaki Toyoda, 1975. "A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems," Management Science, INFORMS, vol. 21(12), pages 1417-1427, August.
    4. Nauss, Robert M., 1978. "The 0-1 knapsack problem with multiple choice constraints," European Journal of Operational Research, Elsevier, vol. 2(2), pages 125-131, March.
    5. David Pisinger, 1997. "A Minimal Algorithm for the 0-1 Knapsack Problem," Operations Research, INFORMS, vol. 45(5), pages 758-767, October.
    6. George B. Dantzig, 1957. "Discrete-Variable Extremum Problems," Operations Research, INFORMS, vol. 5(2), pages 266-288, April.
    7. Pisinger, David, 1995. "A minimal algorithm for the multiple-choice knapsack problem," European Journal of Operational Research, Elsevier, vol. 83(2), pages 394-410, June.
    8. Beasley, J. E. & Chu, P. C., 1996. "A genetic algorithm for the set covering problem," European Journal of Operational Research, Elsevier, vol. 94(2), pages 392-404, October.
    9. Silvano Martello & David Pisinger & Paolo Toth, 1999. "Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 45(3), pages 414-424, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mhand Hifi & Slim Sadfi & Abdelkader Sbihi, 2004. "An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-03322716, HAL.
    2. Abdelkader Sbihi, 2007. "A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 13(4), pages 337-351, May.
    3. Sbihi, Abdelkader, 2010. "A cooperative local search-based algorithm for the Multiple-Scenario Max-Min Knapsack Problem," European Journal of Operational Research, Elsevier, vol. 202(2), pages 339-346, April.
    4. M Hifi & M Michrafy & A Sbihi, 2004. "Heuristic algorithms for the multiple-choice multidimensional knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(12), pages 1323-1332, December.
    5. Wishon, Christopher & Villalobos, J. Rene, 2016. "Robust efficiency measures for linear knapsack problem variants," European Journal of Operational Research, Elsevier, vol. 254(2), pages 398-409.
    6. Zhong, Tao & Young, Rhonda, 2010. "Multiple Choice Knapsack Problem: Example of planning choice in transportation," Evaluation and Program Planning, Elsevier, vol. 33(2), pages 128-137, May.
    7. B. Golany & N. Goldberg & U. Rothblum, 2015. "Allocating multiple defensive resources in a zero-sum game setting," Annals of Operations Research, Springer, vol. 225(1), pages 91-109, February.
    8. M Hifi & M Michrafy, 2006. "A reactive local search-based algorithm for the disjunctively constrained knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(6), pages 718-726, June.
    9. Boysen, Nils & Fliedner, Malte, 2008. "A versatile algorithm for assembly line balancing," European Journal of Operational Research, Elsevier, vol. 184(1), pages 39-56, January.
    10. Yuji Nakagawa & Ross J. W. James & César Rego & Chanaka Edirisinghe, 2014. "Entropy-Based Optimization of Nonlinear Separable Discrete Decision Models," Management Science, INFORMS, vol. 60(3), pages 695-707, March.
    11. Ghosh, Diptesh & Bandyopadhyay, Tathagata, 2006. "Spotting Difficult Weakly Correlated Binary Knapsack Problems," IIMA Working Papers WP2006-01-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    12. Edward Y H Lin & Chung-Min Wu, 2004. "The multiple-choice multi-period knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(2), pages 187-197, February.
    13. Mhand Hifi & Hedi Mhalla & Slim Sadfi, 2005. "Sensitivity of the Optimum to Perturbations of the Profit or Weight of an Item in the Binary Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 10(3), pages 239-260, November.
    14. Toth, Paolo, 2000. "Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 125(2), pages 222-238, September.
    15. Drexl, Andreas & Jørnsten, Kurt, 2007. "Pricing the multiple-choice nested knapsack problem," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 626, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    16. Michel, S. & Perrot, N. & Vanderbeck, F., 2009. "Knapsack problems with setups," European Journal of Operational Research, Elsevier, vol. 196(3), pages 909-918, August.
    17. Klein, Rachelle S. & Luss, Hanan & Rothblum, Uriel G., 1995. "Multiperiod allocation of substitutable resources," European Journal of Operational Research, Elsevier, vol. 85(3), pages 488-503, September.
    18. David Pisinger, 2000. "A Minimal Algorithm for the Bounded Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 12(1), pages 75-82, February.
    19. Silvano Martello & Paolo Toth, 2003. "An Exact Algorithm for the Two-Constraint 0--1 Knapsack Problem," Operations Research, INFORMS, vol. 51(5), pages 826-835, October.
    20. Haijian Si & Stylianos Kavadias & Christoph Loch, 2022. "Managing innovation portfolios: From project selection to portfolio design," Production and Operations Management, Production and Operations Management Society, vol. 31(12), pages 4572-4588, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hal:journl:halshs-03322716. See general information about how to correct material in RePEc.

    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 CitEc recognized a bibliographic reference but did not link an item in RePEc 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.