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

Supermodularity and Affine Policies in Dynamic Robust Optimization

Author

Listed:
  • Dan A. Iancu

    (Graduate School of Business, Stanford University, Stanford, California 94305)

  • Mayank Sharma

    (IBM T. J. Watson Research Center, Yorktown Heights, New York 10598)

  • Maxim Sviridenko

    (Computer Science Department, University of Warwick, Coventry, CV4 7AL, United Kingdom)

Abstract

This paper considers a particular class of dynamic robust optimization problems, where a large number of decisions must be made in the first stage, which consequently fix the constraints and cost structure underlying a one-dimensional, linear dynamical system. We seek to bridge two classical paradigms for solving such problems, namely, (1) dynamic programming (DP), and (2) policies parameterized in model uncertainties (also known as decision rules), obtained by solving tractable convex optimization problems.We show that if the uncertainty sets are integer sublattices of the unit hypercube, the DP value functions are convex and supermodular in the uncertain parameters, and a certain technical condition is satisfied, then decision rules that are affine in the uncertain parameters are optimal. We also derive conditions under which such rules can be obtained by optimizing simple (i.e., linear) objective functions over the uncertainty sets. Our results suggest new modeling paradigms for dynamic robust optimization, and our proofs, which bring together ideas from three areas of optimization typically studied separately—robust optimization, combinatorial optimization (the theory of lattice programming and supermodularity), and global optimization (the theory of concave envelopes)—may be of independent interest.We exemplify our findings in a class of applications concerning the design of flexible production processes, where a retailer seeks to optimally compute a set of strategic decisions (before the start of a selling season), as well as in-season replenishment policies. We show that, when the costs incurred are jointly convex, replenishment policies that depend linearly on the realized demands are optimal. When the costs are also piecewise affine, all the optimal decisions can be found by solving a single linear program of small size (when all decisions are continuous) or a mixed-integer, linear program of the same size (when some strategic decisions are discrete).

Suggested Citation

  • Dan A. Iancu & Mayank Sharma & Maxim Sviridenko, 2013. "Supermodularity and Affine Policies in Dynamic Robust Optimization," Operations Research, INFORMS, vol. 61(4), pages 941-956, August.
    • Handle: RePEc:inm:oropre:v:61:y:2013:i:4:p:941-956
    DOI: 10.1287/opre.2013.1172
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2013.1172
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2013.1172?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. Lars Peter Hansen & Thomas J Sargent, 2014. "Robust Control and Model Uncertainty," World Scientific Book Chapters, in: UNCERTAINTY WITHIN ECONOMIC MODELS, chapter 5, pages 145-154, World Scientific Publishing Co. Pte. Ltd..
    2. Andrew J. Clark & Herbert Scarf, 2004. "Optimal Policies for a Multi-Echelon Inventory Problem," Management Science, INFORMS, vol. 50(12_supple), pages 1782-1790, December.
    3. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    4. Epstein, Larry G. & Schneider, Martin, 2003. "Recursive multiple-priors," Journal of Economic Theory, Elsevier, vol. 113(1), pages 1-31, November.
    5. 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.
    6. Warren H. Hausman, 1969. "Sequential Decision Problems: A Model to Exploit Existing Forecasters," Management Science, INFORMS, vol. 16(2), pages 93-111, October.
    7. 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.
    8. Paul Zipkin, 2008. "On the Structure of Lost-Sales Inventory Models," Operations Research, INFORMS, vol. 56(4), pages 937-944, August.
    9. A. Charnes & W. W. Cooper & G. H. Symonds, 1958. "Cost Horizons and Certainty Equivalents: An Approach to Stochastic Programming of Heating Oil," Management Science, INFORMS, vol. 4(3), pages 235-263, April.
    10. Arthur F. Veinott, Jr., 1966. "The Status of Mathematical Inventory Theory," Management Science, INFORMS, vol. 12(11), pages 745-777, July.
    11. Woonghee Tim Huh & Ganesh Janakiraman, 2010. "On the Optimal Policy Structure in Serial Inventory Systems with Lost Sales," Operations Research, INFORMS, vol. 58(2), pages 486-491, April.
    12. Stephen C. Graves & David B. Kletter & William B. Hetzel, 1998. "A Dynamic Model for Requirements Planning with Application to Supply Chain Optimization," Operations Research, INFORMS, vol. 46(3-supplem), pages 35-49, June.
    13. Joel Goh & Melvyn Sim, 2010. "Distributionally Robust Optimization and Its Tractable Approximations," Operations Research, INFORMS, vol. 58(4-part-1), pages 902-917, August.
    14. 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.
    15. Li Chen & Hau L. Lee, 2009. "Information Sharing and Order Variability Control Under a Generalized Demand Model," Management Science, INFORMS, vol. 55(5), pages 781-797, May.
    16. Chuen-Teck See & Melvyn Sim, 2010. "Robust Approximation to Multiperiod Inventory Management," Operations Research, INFORMS, vol. 58(3), pages 583-594, June.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. Yun Fong Lim & Chen Wang, 2017. "Inventory Management Based on Target-Oriented Robust Optimization," Management Science, INFORMS, vol. 63(12), pages 4409-4427, December.
    3. 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.
    4. 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.
    5. Wang, Yu & Zhang, Yu & Tang, Jiafu, 2019. "A distributionally robust optimization approach for surgery block allocation," European Journal of Operational Research, Elsevier, vol. 273(2), pages 740-753.
    6. Jiankun Sun & Jan A. Van Mieghem, 2019. "Robust Dual Sourcing Inventory Management: Optimality of Capped Dual Index Policies and Smoothing," Manufacturing & Service Operations Management, INFORMS, vol. 21(4), pages 912-931, October.
    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. Joel Goh & Melvyn Sim, 2011. "Robust Optimization Made Easy with ROME," Operations Research, INFORMS, vol. 59(4), pages 973-985, August.
    9. Xin, Linwei & Goldberg, David A., 2021. "Time (in)consistency of multistage distributionally robust inventory models with moment constraints," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1127-1141.
    10. 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.
    11. Dimitris Bertsimas & Melvyn Sim & Meilin Zhang, 2019. "Adaptive Distributionally Robust Optimization," Management Science, INFORMS, vol. 65(2), pages 604-618, February.
    12. 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.
    13. 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.
    14. 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.
    15. Tong Wang & Xiting Gong & Sean X. Zhou, 2017. "Dynamic Inventory Management with Total Minimum Order Commitments and Two Supply Options," Operations Research, INFORMS, vol. 65(5), pages 1285-1302, October.
    16. Shao-Wei Lam & Tsan Sheng Ng & Melvyn Sim & Jin-Hwa Song, 2013. "Multiple Objectives Satisficing Under Uncertainty," Operations Research, INFORMS, vol. 61(1), pages 214-227, February.
    17. 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.
    18. Gorissen, Bram L. & Yanıkoğlu, İhsan & den Hertog, Dick, 2015. "A practical guide to robust optimization," Omega, Elsevier, vol. 53(C), pages 124-137.
    19. Zhi Chen & Melvyn Sim & Huan Xu, 2019. "Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets," Operations Research, INFORMS, vol. 67(5), pages 1328-1344, September.
    20. Metzker Soares, Paula & Thevenin, Simon & Adulyasak, Yossiri & Dolgui, Alexandre, 2024. "Adaptive robust optimization for lot-sizing under yield uncertainty," European Journal of Operational Research, Elsevier, vol. 313(2), pages 513-526.

    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:61:y:2013:i:4:p:941-956. 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.