IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v45y1997i5p768-778.html
   My bibliography  Save this article

Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems

Author

Listed:
  • Silvano Martello

    (University of Bologna, Italy)

  • Paolo Toth

    (University of Bologna, Italy)

Abstract

It is well-known that many instances of the 0-1 knapsack problem can be effectively solved to optimality also for very large values of n (the number of binary variables), while other instances cannot be solved for n equal to only a few hundreds. We propose upper bounds obtained from the mathematical model of the problem by adding valid inequalities on the cardinality of an optimal solution, and relaxing it in a Lagrangian fashion. We then introduce a specialized iterative technique for determining the optimal Lagrangian multipliers in polynomial time. A branch-and-bound algorithm is finally developed. Computational experiments prove that several classes of hard instances are effectively solved even for large values of n .

Suggested Citation

  • Silvano Martello & Paolo Toth, 1997. "Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems," Operations Research, INFORMS, vol. 45(5), pages 768-778, October.
    • Handle: RePEc:inm:oropre:v:45:y:1997:i:5:p:768-778
    DOI: 10.1287/opre.45.5.768
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.45.5.768
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.45.5.768?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. 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.
    2. Mervat Chouman & Teodor Gabriel Crainic & Bernard Gendron, 2018. "The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 143-184, June.
    3. 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.
    4. Mervat Chouman & Teodor Gabriel Crainic & Bernard Gendron, 2017. "Commodity Representations and Cut-Set-Based Inequalities for Multicommodity Capacitated Fixed-Charge Network Design," Transportation Science, INFORMS, vol. 51(2), pages 650-667, May.
    5. 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.
    6. Charles H. Reilly, 2009. "Synthetic Optimization Problem Generation: Show Us the Correlations!," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 458-467, August.
    7. Mhand Hifi & Rym M'Hallah, 2005. "An Exact Algorithm for Constrained Two-Dimensional Two-Staged Cutting Problems," Operations Research, INFORMS, vol. 53(1), pages 140-150, February.
    8. Arnaud Fréville & SaÏd Hanafi, 2005. "The Multidimensional 0-1 Knapsack Problem—Bounds and Computational Aspects," Annals of Operations Research, Springer, vol. 139(1), pages 195-227, October.
    9. 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.
    10. Markus Leitner & Andrea Lodi & Roberto Roberti & Claudio Sole, 2024. "An Exact Method for (Constrained) Assortment Optimization Problems with Product Costs," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 479-494, March.

    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:oropre:v:45:y:1997:i:5:p:768-778. 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.