IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v30y1984i6p765-771.html
   My bibliography  Save this article

A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem

Author

Listed:
  • Silvano Martello

    (Istituto di Automatica, University of Bologna, Bologna, Italy)

  • Paolo Toth

    (Istituto di Informatica e Sistemistica, University of Firenze, Firenze, Italy)

Abstract

Given n items, each having a weight w i , and a container of capacity W, the Subset-Sum Problem (SSP) is to select a subset of the items whose total weight is closest to, without exceeding, W. The paper presents a mixed approach (depth first search-dynamic programming) to the exact solution of the problem. An extensive computational experience is presented, comparing the proposed algorithm with that of Ahrens-Finke, as well as with the Balas-Zemel algorithm for large problems. Both "easy" and "hard" problems with values of n up to 10,000 are considered.

Suggested Citation

  • Silvano Martello & Paolo Toth, 1984. "A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem," Management Science, INFORMS, vol. 30(6), pages 765-771, June.
    • Handle: RePEc:inm:ormnsc:v:30:y:1984:i:6:p:765-771
    DOI: 10.1287/mnsc.30.6.765
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.30.6.765
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.30.6.765?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

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


    Cited by:

    1. Gérard Cornuéjols & Milind Dawande, 1999. "A Class of Hard Small 0-1 Programs," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 205-210, May.
    2. 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.
    3. Dahmani, Isma & Hifi, Mhand & Wu, Lei, 2016. "An exact decomposition algorithm for the generalized knapsack sharing problem," European Journal of Operational Research, Elsevier, vol. 252(3), pages 761-774.
    4. Kellerer, Hans & Mansini, Renata & Speranza, Maria Grazia, 2000. "Two linear approximation algorithms for the subset-sum problem," European Journal of Operational Research, Elsevier, vol. 120(2), pages 289-296, January.
    5. 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.
    6. Soma, Nei Yoshihiro & Toth, Paolo, 2002. "An exact algorithm for the subset sum problem," European Journal of Operational Research, Elsevier, vol. 136(1), pages 57-66, January.
    7. Nicholas G. Hall & Marc E. Posner, 2007. "Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures," Operations Research, INFORMS, vol. 55(4), pages 703-716, August.
    8. Yang Yang, 2024. "An Improved Unbounded-DP Algorithm for the Unbounded Knapsack Problem with Bounded Coefficients," Mathematics, MDPI, vol. 12(12), pages 1-12, June.

    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:inm:ormnsc:v:30:y:1984:i:6:p:765-771. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.