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

Robust Dual Dynamic Programming

Author

Listed:
  • Angelos Georghiou

    (Desautels Faculty of Management, McGill University, Montreal, Quebec H3A 1G5, Canada)

  • Angelos Tsoukalas

    (Olayan School of Business, American University of Beirut, Beirut 1107–2020, Lebanon)

  • Wolfram Wiesemann

    (Imperial College Business School, Imperial College London, London SW7 2AZ, United Kingdom)

Abstract

In the paper “Robust Dual Dynamic Programming,” Angelos Georghiou, Angelos Tsoukalas, and Wolfram Wiesemann propose a novel solution scheme for addressing planning problems with long horizons. Such problems can be formulated as multistage robust optimization problems. The proposed method takes advantage of the decomposable nature of these problems by bounding the costs arising in the future stages through lower and upper cost-to-go functions. The proposed scheme does not require a relatively complete recourse, and it offers deterministic upper and lower bounds throughout the execution of the algorithm. The promising performance of the algorithm is shown in a stylized inventory-management problem in which the proposed algorithm achieved the optimal solution in problem instances with 100 time stages in a few minutes.

Suggested Citation

  • Angelos Georghiou & Angelos Tsoukalas & Wolfram Wiesemann, 2019. "Robust Dual Dynamic Programming," Operations Research, INFORMS, vol. 67(3), pages 813-830, May.
    • Handle: RePEc:inm:oropre:v:67:y:2019:i:3:p:813-830
    DOI: 10.1287/opre.2018.1835
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2018.1835
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2018.1835?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. 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.
    2. Dimitris Bertsimas & Iain Dunning, 2016. "Multistage Robust Mixed-Integer Optimization with Adaptive Partitions," Operations Research, INFORMS, vol. 64(4), pages 980-998, August.
    3. Dan A. Iancu & Nikolaos Trichakis, 2014. "Pareto Efficiency in Robust Optimization," Management Science, INFORMS, vol. 60(1), pages 130-147, January.
    4. Dimitris Bertsimas & Dan A. Iancu & Pablo A. Parrilo, 2010. "Optimality of Affine Policies in Multistage Robust Optimization," Mathematics of Operations Research, INFORMS, vol. 35(2), pages 363-394, May.
    5. 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.
    6. Chrysanthos E. Gounaris & Wolfram Wiesemann & Christodoulos A. Floudas, 2013. "The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty," Operations Research, INFORMS, vol. 61(3), pages 677-693, June.
    7. 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.
    8. Francois V. Louveaux, 1980. "A Solution Method for Multistage Stochastic Programs with Recourse with Application to an Energy Investment Problem," Operations Research, INFORMS, vol. 28(4), pages 889-902, August.
    9. Erick Delage & Yinyu Ye, 2010. "Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems," Operations Research, INFORMS, vol. 58(3), pages 595-612, June.
    10. 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.
    11. Wolfram Wiesemann & Daniel Kuhn & Melvyn Sim, 2014. "Distributionally Robust Convex Optimization," Operations Research, INFORMS, vol. 62(6), pages 1358-1376, December.
    12. LOUVEAUX, François V., 1980. "A solution method for multistage stochastic programs with recourse with application to an energy investment problem," LIDAM Reprints CORE 415, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. de Ruiter, Frans & Brekelmans, Ruud & den Hertog, Dick, 2016. "The impact of the existence of multiple adjustable robust solutions," Other publications TiSEM eabf3802-3965-40ef-b26d-f, Tilburg University, School of Economics and Management.
    14. Xin Chen & Yuhan Zhang, 2009. "Uncertain Linear Programs: Extended Affinely Adjustable Robust Counterparts," Operations Research, INFORMS, vol. 57(6), pages 1469-1482, December.
    15. Shapiro, Alexander, 2011. "Analysis of stochastic dual dynamic programming method," European Journal of Operational Research, Elsevier, vol. 209(1), pages 63-72, February.
    16. Alexander Shapiro & Wajdi Tekaya & Murilo Pereira Soares & Joari Paulo da Costa, 2013. "Worst-Case-Expectation Approach to Optimization Under Uncertainty," Operations Research, INFORMS, vol. 61(6), pages 1435-1449, December.
    17. Joel Goh & Melvyn Sim, 2010. "Distributionally Robust Optimization and Its Tractable Approximations," Operations Research, INFORMS, vol. 58(4-part-1), pages 902-917, August.
    18. Xin Chen & Melvyn Sim & Peng Sun & Jiawei Zhang, 2008. "A Linear Decision-Based Approximation Approach to Stochastic Programming," Operations Research, INFORMS, vol. 56(2), pages 344-357, April.
    19. John R. Birge, 1985. "Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs," Operations Research, INFORMS, vol. 33(5), pages 989-1007, October.
    20. Alexander Shapiro, 2016. "Rectangular Sets of Probability Measures," Operations Research, INFORMS, vol. 64(2), pages 528-541, April.
    21. T. L. Magnanti & J. F. Shapiro & M. H. Wagner, 1976. "Generalized Linear Programming Solves the Dual," Management Science, INFORMS, vol. 22(11), pages 1195-1203, July.
    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. Dimitris Bertsimas & Shimrit Shtern & Bradley Sturt, 2023. "A Data-Driven Approach to Multistage Stochastic Linear Optimization," Management Science, INFORMS, vol. 69(1), pages 51-74, January.
    2. Glomb, Lukas & Liers, Frauke & Rösel, Florian, 2022. "A rolling-horizon approach for multi-period optimization," European Journal of Operational Research, Elsevier, vol. 300(1), pages 189-206.
    3. Xiong, Houbo & Yan, Mingyu & Guo, Chuangxin & Ding, Yi & Zhou, Yue, 2023. "DP based multi-stage ARO for coordinated scheduling of CSP and wind energy with tractable storage scheme: Tight formulation and solution technique," Applied Energy, Elsevier, vol. 333(C).
    4. Haodong Yu & Jie Sun & Yanjun Wang, 2021. "A time-consistent Benders decomposition method for multistage distributionally robust stochastic optimization with a scenario tree structure," Computational Optimization and Applications, Springer, vol. 79(1), pages 67-99, May.
    5. Yıldıran, Uğur, 2023. "Robust multi-stage economic dispatch with renewable generation and storage," European Journal of Operational Research, Elsevier, vol. 309(2), pages 890-909.
    6. 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.
    7. Xiong, Houbo & Zhou, Yue & Guo, Chuangxin & Ding, Yi & Luo, Fengji, 2023. "Multi-stage risk-based assessment for wind energy accommodation capability: A robust and non-anticipative method," Applied Energy, Elsevier, vol. 350(C).
    8. Luyu Wang & Houbo Xiong & Yunhui Shi & Chuangxin Guo, 2023. "Rolling Horizon Robust Real-Time Economic Dispatch with Multi-Stage Dynamic Modeling," Mathematics, MDPI, vol. 11(11), pages 1-20, June.
    9. François Clautiaux & Boris Detienne & Henri Lefebvre, 2023. "A two-stage robust approach for minimizing the weighted number of tardy jobs with objective uncertainty," Journal of Scheduling, Springer, vol. 26(2), pages 169-191, April.
    10. 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.
    11. Park, Jangho & Bayraksan, Güzin, 2023. "A multistage distributionally robust optimization approach to water allocation under climate uncertainty," European Journal of Operational Research, Elsevier, vol. 306(2), pages 849-871.
    12. Qiu, Haifeng & Sun, Qirun & Lu, Xi & Beng Gooi, Hoay & Zhang, Suhan, 2022. "Optimality-feasibility-aware multistage unit commitment considering nonanticipative realization of uncertainty," Applied Energy, Elsevier, vol. 327(C).

    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. Bakker, Hannah & Dunke, Fabian & Nickel, Stefan, 2020. "A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice," Omega, Elsevier, vol. 96(C).
    2. 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.
    3. 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.
    4. 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.
    5. Angelos Georghiou & Daniel Kuhn & Wolfram Wiesemann, 2019. "The decision rule approach to optimization under uncertainty: methodology and applications," Computational Management Science, Springer, vol. 16(4), pages 545-576, October.
    6. 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.
    7. Rahal, Said & Papageorgiou, Dimitri J. & Li, Zukui, 2021. "Hybrid strategies using linear and piecewise-linear decision rules for multistage adaptive linear optimization," European Journal of Operational Research, Elsevier, vol. 290(3), pages 1014-1030.
    8. Haolin Ruan & Zhi Chen & Chin Pang Ho, 2023. "Adjustable Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1002-1023, September.
    9. 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.
    10. 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.
    11. 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.
    12. 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," Discussion Paper 2016-039, Tilburg University, Center for Economic Research.
    13. 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.
    14. 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.
    15. Ayşe N. Arslan & Boris Detienne, 2022. "Decomposition-Based Approaches for a Class of Two-Stage Robust Binary Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 857-871, March.
    16. 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.
    17. Dimitris Bertsimas & Melvyn Sim & Meilin Zhang, 2019. "Adaptive Distributionally Robust Optimization," Management Science, INFORMS, vol. 65(2), pages 604-618, February.
    18. Mengshi Lu & Zuo‐Jun Max Shen, 2021. "A Review of Robust Operations Management under Model Uncertainty," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1927-1943, June.
    19. Sergey S. Ketkov, 2023. "On the Multistage Shortest Path Problem Under Distributional Uncertainty," Journal of Optimization Theory and Applications, Springer, vol. 197(1), pages 277-308, April.
    20. Cohen, Izack & Postek, Krzysztof & Shtern, Shimrit, 2023. "An adaptive robust optimization model for parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 306(1), pages 83-104.

    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:67:y:2019:i:3:p:813-830. 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.