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

An Exact Algorithm for the Two-Constraint 0--1 Knapsack Problem

Author

Listed:
  • Silvano Martello

    (DEIS, University of Bologna, Bologna, Italy)

  • Paolo Toth

    (DEIS, University of Bologna, Bologna, Italy)

Abstract

We consider a knapsack problem in which each item has two types of weight and the container has two types of capacity. We discuss the surrogate, Lagrangian, and continuous relaxations, and give an effective method to determine the optimal Lagrangian and surrogate multipliers associated with the continuous relaxation of the problem. These results are used to obtain an exact branch-and-bound algorithm, which also includes heuristic procedures and a reduction technique. The performance of bounds and algorithms is evaluated through extensive computational experiments.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:oropre:v:51:y:2003:i:5:p:826-835
    DOI: 10.1287/opre.51.5.826.16757
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.51.5.826.16757
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.51.5.826.16757?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
    ---><---

    References listed on IDEAS

    as
    1. Bagchi, Ansuman & Bhattacharyya, Nalinaksha & Chakravarti, Nilotpal, 1996. "LP relaxation of the two dimensional knapsack problem with box and GUB constraints," European Journal of Operational Research, Elsevier, vol. 89(3), pages 609-617, March.
    2. H. Martin Weingartner & David N. Ness, 1967. "Methods for the Solution of the Multidimensional 0/1 Knapsack Problem," Operations Research, INFORMS, vol. 15(1), pages 83-103, February.
    3. Silvano Martello & Paolo Toth, 1988. "A New Algorithm for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 34(5), pages 633-644, May.
    4. George B. Dantzig, 1957. "Discrete-Variable Extremum Problems," Operations Research, INFORMS, vol. 5(2), pages 266-288, April.
    5. L. Escudero & S. Martello & P. Toth, 1998. "On tightening 0-1 programs based on extensions ofpure 0-1 knapsack and subset-sum problems," Annals of Operations Research, Springer, vol. 81(0), pages 379-404, June.
    6. 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.
    7. Freville, Arnaud & Plateau, Gerard, 1993. "An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 68(3), pages 413-421, August.
    8. Fred Glover, 1975. "Surrogate Constraint Duality in Mathematical Programming," Operations Research, INFORMS, vol. 23(3), pages 434-451, June.
    9. Egon Balas & Eitan Zemel, 1980. "An Algorithm for Large Zero-One Knapsack Problems," Operations Research, INFORMS, vol. 28(5), pages 1130-1154, October.
    10. 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)

    Citations

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


    Cited by:

    1. Federico Della Croce & Christos Koulamas & Vincent T’kindt, 2017. "Minimizing the number of tardy jobs in two-machine settings with common due date," Journal of Combinatorial Optimization, Springer, vol. 34(1), pages 133-140, July.
    2. Wang, Ting & Hu, Qian & Lim, Andrew, 2022. "An exact algorithm for two-dimensional vector packing problem with volumetric weight and general costs," European Journal of Operational Research, Elsevier, vol. 300(1), pages 20-34.
    3. Renata Mansini & M. Grazia Speranza, 2012. "CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 399-415, August.
    4. 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.
    5. Della Croce, Federico & Salassa, Fabio & Scatamacchia, Rosario, 2017. "A new exact approach for the 0–1 Collapsing Knapsack Problem," European Journal of Operational Research, Elsevier, vol. 260(1), pages 56-69.
    6. Yoon, Yourim & Kim, Yong-Hyuk & Moon, Byung-Ro, 2012. "A theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 218(2), pages 366-376.
    7. Katrin Heßler & Stefan Irnich & Tobias Kreiter & Ulrich Pferschy, 2020. "Lexicographic Bin-Packing Optimization for Loading Trucks in a Direct-Shipping System," Working Papers 2009, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    8. 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.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Charles H. Reilly, 2009. "Synthetic Optimization Problem Generation: Show Us the Correlations!," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 458-467, August.
    6. Martello, Silvano & Pisinger, David & Toth, Paolo, 2000. "New trends in exact algorithms for the 0-1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 123(2), pages 325-332, June.
    7. Jakob Puchinger & Günther R. Raidl & Ulrich Pferschy, 2010. "The Multidimensional Knapsack Problem: Structure and Algorithms," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 250-265, May.
    8. Marc Goerigk, 2014. "A note on upper bounds to the robust knapsack problem with discrete scenarios," Annals of Operations Research, Springer, vol. 223(1), pages 461-469, December.
    9. Jooken, Jorik & Leyman, Pieter & De Causmaecker, Patrick, 2022. "A new class of hard problem instances for the 0–1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 301(3), pages 841-854.
    10. Cerqueus, Audrey & Przybylski, Anthony & Gandibleux, Xavier, 2015. "Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems," European Journal of Operational Research, Elsevier, vol. 244(2), pages 417-433.
    11. Reilly, Charles H. & Sapkota, Nabin, 2015. "A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances," European Journal of Operational Research, Elsevier, vol. 241(3), pages 642-652.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    18. Yanhong Feng & Xu Yu & Gai-Ge Wang, 2019. "A Novel Monarch Butterfly Optimization with Global Position Updating Operator for Large-Scale 0-1 Knapsack Problems," Mathematics, MDPI, vol. 7(11), pages 1-31, November.
    19. Altay, Nezih & Robinson Jr., Powell E. & Bretthauer, Kurt M., 2008. "Exact and heuristic solution approaches for the mixed integer setup knapsack problem," European Journal of Operational Research, Elsevier, vol. 190(3), pages 598-609, November.
    20. 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.

    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:51:y:2003:i:5:p:826-835. 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: 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.