IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v271y2018i2d10.1007_s10479-018-2908-x.html
   My bibliography  Save this article

A perfect information lower bound for robust lot-sizing problems

Author

Listed:
  • Marcio Costa Santos

    (Université Libre de Bruxelles
    INRIA Lille Nord-Europe)

  • Michael Poss

    (Université de Montpellier)

  • Dritan Nace

    (Sorbonne universités)

Abstract

Robust multi-stage linear optimization is hard computationally and only small problems can be solved exactly. Hence, robust multi-stage linear problems are typically addressed heuristically through decision rules, which provide upper bounds for the optimal solution costs of the problems. We investigate in this paper lower bounds inspired by the perfect information relaxation used in stochastic programming. Specifically, we study the uncapacitated robust lot-sizing problem, showing that different versions of the problem become tractable whenever the non-anticipativity constraints are relaxed. Hence, we can solve the resulting problem efficiently, obtaining a lower bound for the optimal solution cost of the original problem. We compare numerically the solution time and the quality of the new lower bound with the dual affine decision rules that have been proposed by Kuhn et al. (Math Program 130:177–209, 2011).

Suggested Citation

  • Marcio Costa Santos & Michael Poss & Dritan Nace, 2018. "A perfect information lower bound for robust lot-sizing problems," Annals of Operations Research, Springer, vol. 271(2), pages 887-913, December.
    • Handle: RePEc:spr:annopr:v:271:y:2018:i:2:d:10.1007_s10479-018-2908-x
    DOI: 10.1007/s10479-018-2908-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-018-2908-x
    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/s10479-018-2908-x?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. M. Avriel & A. C. Williams, 1970. "The Value of Information and Stochastic Programming," Operations Research, INFORMS, vol. 18(5), pages 947-954, October.
    2. C. C. Huang & I. Vertinsky & W. T. Ziemba, 1977. "Sharp Bounds on the Value of Perfect Information," Operations Research, INFORMS, vol. 25(1), pages 128-139, February.
    3. Postek, K.S. & den Hertog, D., 2016. "Multi-stage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty set (Revision of CentER Discussion Paper 2014-056)," Other publications TiSEM 08442e3a-d1eb-42b3-8f13-8, Tilburg University, School of Economics and Management.
    4. Frans J. C. T. Ruiter & Aharon Ben-Tal & Ruud C. M. Brekelmans & Dick Hertog, 2017. "Robust optimization of uncertain multistage inventory systems with inexact data in decision rules," Computational Management Science, Springer, vol. 14(1), pages 45-66, January.
    5. Krzysztof Postek & Dick den Hertog, 2016. "Multistage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty Set," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 553-574, August.
    6. X. M. Hu & D. Ralph, 2004. "Convergence of a Penalty Method for Mathematical Programming with Complementarity Constraints," Journal of Optimization Theory and Applications, Springer, vol. 123(2), pages 365-390, November.
    7. Aharon Ben-Tal & Boaz Golany & Arkadi Nemirovski & Jean-Philippe Vial, 2005. "Retailer-Supplier Flexible Commitments Contracts: A Robust Optimization Approach," Manufacturing & Service Operations Management, INFORMS, vol. 7(3), pages 248-271, February.
    8. Josette Ayoub & Michael Poss, 2016. "Decomposition for adjustable robust linear optimization subject to uncertainty polytope," Computational Management Science, Springer, vol. 13(2), pages 219-239, April.
    9. Pochet, Y. & Wolsey, L. A., 1994. "Polyhedra for lot-sizing with Wagner-Whitin costs," LIDAM Reprints CORE 1129, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. A. Ben-Tal & A. Nemirovski, 1998. "Robust Convex Optimization," Mathematics of Operations Research, INFORMS, vol. 23(4), pages 769-805, November.
    11. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    12. Gorissen, Bram L. & den Hertog, Dick, 2013. "Robust counterparts of inequalities containing sums of maxima of linear functions," European Journal of Operational Research, Elsevier, vol. 227(1), pages 30-43.
    13. Dimitris Bertsimas & Aurélie Thiele, 2006. "A Robust Optimization Approach to Inventory Theory," Operations Research, INFORMS, vol. 54(1), pages 150-168, February.
    14. Joel Goh & Melvyn Sim, 2010. "Distributionally Robust Optimization and Its Tractable Approximations," Operations Research, INFORMS, vol. 58(4-part-1), pages 902-917, August.
    15. Dimitris Bertsimas & Angelos Georghiou, 2015. "Design of Near Optimal Decision Rules in Multistage Adaptive Mixed-Integer Optimization," Operations Research, INFORMS, vol. 63(3), pages 610-627, June.
    16. repec:spr:pharme:v:21:y:2003:i:12:p:839-851 is not listed on IDEAS
    17. Xin Chen & Yuhan Zhang, 2009. "Uncertain Linear Programs: Extended Affinely Adjustable Robust Counterparts," Operations Research, INFORMS, vol. 57(6), pages 1469-1482, December.
    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. Rostami, Salim & Creemers, Stefan & Leus, Roel, 2024. "Maximizing the net present value of a project under uncertainty: Activity delays and dynamic policies," European Journal of Operational Research, Elsevier, vol. 317(1), pages 16-24.
    2. Andrew J. Keith & Darryl K. Ahner, 2021. "A survey of decision making and optimization under uncertainty," Annals of Operations Research, Springer, vol. 300(2), pages 319-353, May.
    3. Sixiang Zhao, 2023. "Decision rule-based method in solving adjustable robust capacity expansion problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 97(2), pages 259-286, April.

    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. Nicolas Kämmerling & Jannis Kurtz, 2020. "Oracle-based algorithms for binary two-stage robust optimization," Computational Optimization and Applications, Springer, vol. 77(2), pages 539-569, November.
    2. Christoph Buchheim & Jannis Kurtz, 2018. "Robust combinatorial optimization under convex and discrete cost uncertainty," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(3), pages 211-238, September.
    3. Yanıkoğlu, İhsan & Gorissen, Bram L. & den Hertog, Dick, 2019. "A survey of adjustable robust optimization," European Journal of Operational Research, Elsevier, vol. 277(3), pages 799-813.
    4. Angelos Georghiou & Angelos Tsoukalas & Wolfram Wiesemann, 2020. "A Primal–Dual Lifting Scheme for Two-Stage Robust Optimization," Operations Research, INFORMS, vol. 68(2), pages 572-590, March.
    5. Hamed Mamani & Shima Nassiri & Michael R. Wagner, 2017. "Closed-Form Solutions for Robust Inventory Management," Management Science, INFORMS, vol. 63(5), pages 1625-1643, May.
    6. Feng, Wei & Feng, Yiping & Zhang, Qi, 2021. "Multistage robust mixed-integer optimization under endogenous uncertainty," European Journal of Operational Research, Elsevier, vol. 294(2), pages 460-475.
    7. Xie, Chen & Wang, Liangquan & Yang, Chaolin, 2021. "Robust inventory management with multiple supply sources," European Journal of Operational Research, Elsevier, vol. 295(2), pages 463-474.
    8. Amir Ardestani-Jaafari & Erick Delage, 2016. "Robust Optimization of Sums of Piecewise Linear Functions with Application to Inventory Problems," Operations Research, INFORMS, vol. 64(2), pages 474-494, April.
    9. Marcio Costa Santos & Agostinho Agra & Michael Poss, 2020. "Robust inventory theory with perishable products," Annals of Operations Research, Springer, vol. 289(2), pages 473-494, June.
    10. Angelos Georghiou & Angelos Tsoukalas & Wolfram Wiesemann, 2019. "Robust Dual Dynamic Programming," Operations Research, INFORMS, vol. 67(3), pages 813-830, May.
    11. Walid Ben-Ameur & Adam Ouorou & Guanglei Wang & Mateusz Żotkiewicz, 2018. "Multipolar robust optimization," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 395-434, December.
    12. Jianzhe Zhen & Ahmadreza Marandi & Danique de Moor & Dick den Hertog & Lieven Vandenberghe, 2022. "Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2410-2427, September.
    13. Andreas Thorsen & Tao Yao, 2017. "Robust inventory control under demand and lead time uncertainty," Annals of Operations Research, Springer, vol. 257(1), pages 207-236, October.
    14. Postek, Krzysztof & Romeijnders, Ward & den Hertog, Dick & van der Vlerk, Maartne H., 2016. "Efficient Methods for Several Classes of Ambiguous Stochastic Programming Problems under Mean-MAD Information," Other publications TiSEM a03f895f-b941-41a9-84e0-b, Tilburg University, School of Economics and Management.
    15. Anirudh Subramanyam & Frank Mufalli & José M. Lí?nez-Aguirre & Jose M. Pinto & Chrysanthos E. Gounaris, 2021. "Robust Multiperiod Vehicle Routing Under Customer Order Uncertainty," Operations Research, INFORMS, vol. 69(1), pages 30-60, January.
    16. Farough Motamed Nasab & Zukui Li, 2023. "Multistage Adaptive Robust Binary Optimization: Uncertainty Set Lifting versus Partitioning through Breakpoints Optimization," Mathematics, MDPI, vol. 11(18), pages 1-24, September.
    17. Dimitris Bertsimas & Melvyn Sim & Meilin Zhang, 2019. "Adaptive Distributionally Robust Optimization," Management Science, INFORMS, vol. 65(2), pages 604-618, February.
    18. Dimitris Bertsimas & Angelos Georghiou, 2015. "Design of Near Optimal Decision Rules in Multistage Adaptive Mixed-Integer Optimization," Operations Research, INFORMS, vol. 63(3), pages 610-627, June.
    19. Oğuz Solyalı & Jean-François Cordeau & Gilbert Laporte, 2016. "The Impact of Modeling on Robust Inventory Management Under Demand Uncertainty," Management Science, INFORMS, vol. 62(4), pages 1188-1201, April.
    20. Marcus Ang & Yun Fong Lim & Melvyn Sim, 2012. "Robust Storage Assignment in Unit-Load Warehouses," Management Science, INFORMS, vol. 58(11), pages 2114-2130, November.

    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:annopr:v:271:y:2018:i:2:d:10.1007_s10479-018-2908-x. 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.