IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v161y2014i2d10.1007_s10957-013-0319-3.html
   My bibliography  Save this article

Complexity Results and Exact Algorithms for Robust Knapsack Problems

Author

Listed:
  • Fabrice Talla Nobibon

    (PostDoc researcher for Research Foundation—Flanders
    University of Liège
    KU Leuven)

  • Roel Leus

    (KU Leuven)

Abstract

This paper studies the robust knapsack problem, for which solutions are, up to a certain point, immune from data uncertainty. We complement the works found in the literature, where uncertainty affects only the profits or only the weights of the items, by studying the complexity and approximation of the general setting with uncertainty regarding both the profits and the weights, for three different objective functions. Furthermore, we develop a scenario-relaxation algorithm for solving the general problem and present computational results.

Suggested Citation

  • Fabrice Talla Nobibon & Roel Leus, 2014. "Complexity Results and Exact Algorithms for Robust Knapsack Problems," Journal of Optimization Theory and Applications, Springer, vol. 161(2), pages 533-552, May.
    • Handle: RePEc:spr:joptap:v:161:y:2014:i:2:d:10.1007_s10957-013-0319-3
    DOI: 10.1007/s10957-013-0319-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-013-0319-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-013-0319-3?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    2. Grace Y. Lin & Yingdong Lu & David D. Yao, 2008. "The Stochastic Knapsack Revisited: Switch-Over Policies and Dynamic Pricing," Operations Research, INFORMS, vol. 56(4), pages 945-957, August.
    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. ,, 2000. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 16(2), pages 287-299, April.
    5. Anton J. Kleywegt & Jason D. Papastavrou, 1998. "The Dynamic and Stochastic Knapsack Problem," Operations Research, INFORMS, vol. 46(1), pages 17-35, February.
    6. Gang Yu, 1996. "On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications," Operations Research, INFORMS, vol. 44(2), pages 407-415, April.
    7. Rim Kalaï & Daniel Vanderpooten, 2011. "The lexicographic α-robust knapsack problem," Post-Print hal-00820135, HAL.
    8. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2007. "Approximation of min-max and min-max regret versions of some combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 179(2), pages 281-290, June.
    9. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2009. "Min-max and min-max regret versions of combinatorial optimization problems: A survey," European Journal of Operational Research, Elsevier, vol. 197(2), pages 427-438, September.
    10. Eilon, Samuel, 1987. "Application of the knapsack model for budgeting," Omega, Elsevier, vol. 15(6), pages 489-494.
    11. 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. Artur Alves Pessoa & Michael Poss & Ruslan Sadykov & François Vanderbeck, 2021. "Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty," Operations Research, INFORMS, vol. 69(3), pages 739-754, May.
    2. Baldo, Alessandro & Boffa, Matteo & Cascioli, Lorenzo & Fadda, Edoardo & Lanza, Chiara & Ravera, Arianna, 2023. "The polynomial robust knapsack problem," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1424-1434.
    3. Caserta, Marco & Voß, Stefan, 2019. "The robust multiple-choice multidimensional knapsack problem," Omega, Elsevier, vol. 86(C), pages 16-27.

    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. Fabio Furini & Manuel Iori & Silvano Martello & Mutsunori Yagiura, 2015. "Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 392-405, May.
    2. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2009. "Min-max and min-max regret versions of combinatorial optimization problems: A survey," European Journal of Operational Research, Elsevier, vol. 197(2), pages 427-438, September.
    3. Kalaı¨, Rim & Lamboray, Claude & Vanderpooten, Daniel, 2012. "Lexicographic α-robustness: An alternative to min–max criteria," European Journal of Operational Research, Elsevier, vol. 220(3), pages 722-728.
    4. Alireza Amirteimoori & Simin Masrouri, 2021. "DEA-based competition strategy in the presence of undesirable products: An application to paper mills," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 31(2), pages 5-21.
    5. Baldo, Alessandro & Boffa, Matteo & Cascioli, Lorenzo & Fadda, Edoardo & Lanza, Chiara & Ravera, Arianna, 2023. "The polynomial robust knapsack problem," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1424-1434.
    6. Georgios P. Trachanas & Aikaterini Forouli & Nikolaos Gkonis & Haris Doukas, 2020. "Hedging uncertainty in energy efficiency strategies: a minimax regret analysis," Operational Research, Springer, vol. 20(4), pages 2229-2244, December.
    7. Nicholas G. Hall & Daniel Zhuoyu Long & Jin Qi & Melvyn Sim, 2015. "Managing Underperformance Risk in Project Portfolio Selection," Operations Research, INFORMS, vol. 63(3), pages 660-675, June.
    8. Christina Büsing & Sebastian Goderbauer & Arie M. C. A. Koster & Manuel Kutschka, 2019. "Formulations and algorithms for the recoverable $${\varGamma }$$ Γ -robust knapsack problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(1), pages 15-45, March.
    9. Pätzold, Julius & Schöbel, Anita, 2020. "Approximate cutting plane approaches for exact solutions to robust optimization problems," European Journal of Operational Research, Elsevier, vol. 284(1), pages 20-30.
    10. Chassein, André & Goerigk, Marc, 2017. "Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets," European Journal of Operational Research, Elsevier, vol. 258(1), pages 58-69.
    11. Nikulin, Yury, 2006. "Robustness in combinatorial optimization and scheduling theory: An extended annotated bibliography," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 606, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    12. Levorato, Mario & Figueiredo, Rosa & Frota, Yuri, 2022. "Exact solutions for the two-machine robust flow shop with budgeted uncertainty," European Journal of Operational Research, Elsevier, vol. 300(1), pages 46-57.
    13. Carrizosa, Emilio & Goerigk, Marc & Schöbel, Anita, 2017. "A biobjective approach to recoverable robustness based on location planning," European Journal of Operational Research, Elsevier, vol. 261(2), pages 421-435.
    14. Arash Gourtani & Huifu Xu & David Pozo & Tri-Dung Nguyen, 2016. "Robust unit commitment with $$n-1$$ n - 1 security criteria," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 83(3), pages 373-408, June.
    15. Wenqing Chen & Melvyn Sim & Jie Sun & Chung-Piaw Teo, 2010. "From CVaR to Uncertainty Set: Implications in Joint Chance-Constrained Optimization," Operations Research, INFORMS, vol. 58(2), pages 470-485, April.
    16. Stefan Mišković, 2017. "A VNS-LP algorithm for the robust dynamic maximal covering location problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(4), pages 1011-1033, October.
    17. Chassein, André & Dokka, Trivikram & Goerigk, Marc, 2019. "Algorithms and uncertainty sets for data-driven robust shortest path problems," European Journal of Operational Research, Elsevier, vol. 274(2), pages 671-686.
    18. M. J. Naderi & M. S. Pishvaee, 2017. "Robust bi-objective macroscopic municipal water supply network redesign and rehabilitation," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 31(9), pages 2689-2711, July.
    19. Ruiwei Jiang & Siqian Shen & Yiling Zhang, 2017. "Integer Programming Approaches for Appointment Scheduling with Random No-Shows and Service Durations," Operations Research, INFORMS, vol. 65(6), pages 1638-1656, December.
    20. Mínguez, R. & García-Bertrand, R., 2016. "Robust transmission network expansion planning in energy systems: Improving computational performance," European Journal of Operational Research, Elsevier, vol. 248(1), pages 21-32.

    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:spr:joptap:v:161:y:2014:i:2:d:10.1007_s10957-013-0319-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.