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

Price of Correlations in Stochastic Optimization

Author

Listed:
  • Shipra Agrawal

    (Department of Computer Science, Stanford University, Stanford, California 94305)

  • Yichuan Ding

    (Department of Management Science and Engineering, Stanford University, Stanford, California 94305)

  • Amin Saberi

    (Department of Management Science and Engineering, Stanford University, Stanford, California 94305)

  • Yinyu Ye

    (Department of Management Science and Engineering, Stanford University, Stanford, California 94305)

Abstract

When decisions are made in the presence of high-dimensional stochastic data, handling joint distribution of correlated random variables can present a formidable task, both in terms of sampling and estimation as well as algorithmic complexity. A common heuristic is to estimate only marginal distributions and substitute joint distribution by independent (product) distribution. In this paper, we study possible loss incurred on ignoring correlations through a distributionally robust stochastic programming model, and we quantify that loss as price of correlations (POC). Using techniques of cost sharing from game theory, we identify a wide class of problems for which POC has a small upper bound. To our interest, this class will include many stochastic convex programs, uncapacitated facility location, Steiner tree, and submodular functions, suggesting that the intuitive approach of assuming independent distribution acceptably approximates the robust model for these stochastic optimization problems. Additionally, we demonstrate hardness of bounding POC via examples of subadditive and supermodular functions that have large POC. We find that our results are also useful for solving many deterministic optimization problems like welfare maximization, k -dimensional matching, and transportation problems, under certain conditions.

Suggested Citation

  • Shipra Agrawal & Yichuan Ding & Amin Saberi & Yinyu Ye, 2012. "Price of Correlations in Stochastic Optimization," Operations Research, INFORMS, vol. 60(1), pages 150-162, February.
    • Handle: RePEc:inm:oropre:v:60:y:2012:i:1:p:150-162
    DOI: 10.1287/opre.1110.1011
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1110.1011
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1110.1011?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. Hervé Moulin & Scott Shenker, 2001. "Strategyproof sharing of submodular costs:budget balance versus efficiency," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 18(3), pages 511-533.
    2. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    3. Ioana Popescu, 2007. "Robust Mean-Covariance Solutions for Stochastic Optimization," Operations Research, INFORMS, vol. 55(1), pages 98-112, February.
    4. ,, 2000. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 16(2), pages 287-299, April.
    5. 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.
    6. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
    7. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    8. Jinfeng Yue & Bintong Chen & Min-Chiang Wang, 2006. "Expected Value of Distribution Information for the Newsvendor Problem," Operations Research, INFORMS, vol. 54(6), pages 1128-1136, December.
    9. HervÊ Moulin, 1999. "Incremental cost sharing: Characterization by coalition strategy-proofness," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 16(2), pages 279-320.
    10. A. Ben-Tal & A. Nemirovski, 1998. "Robust Convex Optimization," Mathematics of Operations Research, INFORMS, vol. 23(4), pages 769-805, November.
    11. Xin Chen & Melvyn Sim & Peng Sun, 2007. "A Robust Optimization Perspective on Stochastic Programming," Operations Research, INFORMS, vol. 55(6), pages 1058-1071, December.
    12. Joel Goh & Melvyn Sim, 2010. "Distributionally Robust Optimization and Its Tractable Approximations," Operations Research, INFORMS, vol. 58(4-part-1), pages 902-917, August.
    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. Renaud Chicoisne & Fernando Ordóñez & Daniel Espinoza, 2018. "Risk Averse Shortest Paths: A Computational Study," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 539-553, August.
    2. Wang, Changjun & Chen, Shutong, 2020. "A distributionally robust optimization for blood supply network considering disasters," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 134(C).
    3. Paul, Jomon Aliyas & Wang, Xinfang (Jocelyn), 2015. "Robust optimization for United States Department of Agriculture food aid bid allocations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 82(C), pages 129-146.
    4. Cecil Ash & Uday Venkatadri & Claver Diallo & Peter Vanberkel & Ahmed Saif, 2023. "PPE Supply Optimization Under Risks of Disruption from the COVID-19 Pandemic," SN Operations Research Forum, Springer, vol. 4(2), pages 1-29, June.
    5. Benoumechiara Nazih & Bousquet Nicolas & Michel Bertrand & Saint-Pierre Philippe, 2020. "Detecting and modeling critical dependence structures between random inputs of computer models," Dependence Modeling, De Gruyter, vol. 8(1), pages 263-297, January.
    6. Ming Zhao & Nickolas Freeman & Kai Pan, 2023. "Robust Sourcing Under Multilevel Supply Risks: Analysis of Random Yield and Capacity," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 178-195, January.
    7. Shabbir Ahmed & Dimitri J. Papageorgiou, 2013. "Probabilistic Set Covering with Correlations," Operations Research, INFORMS, vol. 61(2), pages 438-452, April.
    8. Silva, Marco & Pedroso, João Pedro & Viana, Ana, 2023. "Stochastic crowd shipping last-mile delivery with correlated marginals and probabilistic constraints," European Journal of Operational Research, Elsevier, vol. 307(1), pages 249-265.
    9. 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.
    10. Zhichao Zheng & Karthik Natarajan & Chung-Piaw Teo, 2016. "Least Squares Approximation to the Distribution of Project Completion Times with Gaussian Uncertainty," Operations Research, INFORMS, vol. 64(6), pages 1406-1421, December.
    11. Steffen Rebennack, 2022. "Data-driven stochastic optimization for distributional ambiguity with integrated confidence region," Journal of Global Optimization, Springer, vol. 84(2), pages 255-293, October.
    12. Mengshi Lu & Lun Ran & Zuo-Jun Max Shen, 2015. "Reliable Facility Location Design Under Uncertain Correlated Disruptions," Manufacturing & Service Operations Management, INFORMS, vol. 17(4), pages 445-455, October.
    13. Benoumechiara Nazih & Bousquet Nicolas & Michel Bertrand & Saint-Pierre Philippe, 2020. "Detecting and modeling critical dependence structures between random inputs of computer models," Dependence Modeling, De Gruyter, vol. 8(1), pages 263-297, January.
    14. Marek Adamczyk & Maxim Sviridenko & Justin Ward, 2016. "Submodular Stochastic Probing on Matroids," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 1022-1038, August.
    15. Miguel A. Lejeune, 2012. "Game Theoretical Approach for Reliable Enhanced Indexation," Decision Analysis, INFORMS, vol. 9(2), pages 146-155, June.
    16. Qi Feng & Justin Jia & J. George Shanthikumar, 2019. "Dynamic Multisourcing with Dependent Supplies," Management Science, INFORMS, vol. 67(6), pages 2770-2786, June.
    17. Sundararajan, Mukund & Yan, Qiqi, 2020. "Robust mechanisms for risk-averse sellers," Games and Economic Behavior, Elsevier, vol. 124(C), pages 644-658.
    18. Sankaranarayanan, Sriram & Feijoo, Felipe & Siddiqui, Sauleh, 2018. "Sensitivity and covariance in stochastic complementarity problems with an application to North American natural gas markets," European Journal of Operational Research, Elsevier, vol. 268(1), pages 25-36.
    19. Arash Asadpour & Hamid Nazerzadeh, 2016. "Maximizing Stochastic Monotone Submodular Functions," Management Science, INFORMS, vol. 62(8), pages 2374-2391, August.

    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. Dimitris Bertsimas & Melvyn Sim & Meilin Zhang, 2019. "Adaptive Distributionally Robust Optimization," Management Science, INFORMS, vol. 65(2), pages 604-618, February.
    2. 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.
    3. L. Jeff Hong & Zhiyuan Huang & Henry Lam, 2021. "Learning-Based Robust Optimization: Procedures and Statistical Guarantees," Management Science, INFORMS, vol. 67(6), pages 3447-3467, June.
    4. Fanwen Meng & Jin Qi & Meilin Zhang & James Ang & Singfat Chu & Melvyn Sim, 2015. "A Robust Optimization Model for Managing Elective Admission in a Public Hospital," Operations Research, INFORMS, vol. 63(6), pages 1452-1467, December.
    5. Steffen Rebennack, 2022. "Data-driven stochastic optimization for distributional ambiguity with integrated confidence region," Journal of Global Optimization, Springer, vol. 84(2), pages 255-293, October.
    6. 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.
    7. Postek, Krzysztof & Ben-Tal, A. & den Hertog, Dick & Melenberg, Bertrand, 2015. "Exact Robust Counterparts of Ambiguous Stochastic Constraints Under Mean and Dispersion Information," Other publications TiSEM d718e419-a375-4707-b206-e, Tilburg University, School of Economics and Management.
    8. Marla, Lavanya & Rikun, Alexander & Stauffer, Gautier & Pratsini, Eleni, 2020. "Robust modeling and planning: Insights from three industrial applications," Operations Research Perspectives, Elsevier, vol. 7(C).
    9. Liu, Kanglin & Li, Qiaofeng & Zhang, Zhi-Hai, 2019. "Distributionally robust optimization of an emergency medical service station location and sizing problem with joint chance constraints," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 79-101.
    10. Joel Goh & Melvyn Sim, 2011. "Robust Optimization Made Easy with ROME," Operations Research, INFORMS, vol. 59(4), pages 973-985, August.
    11. Gabrel, Virginie & Murat, Cécile & Thiele, Aurélie, 2014. "Recent advances in robust optimization: An overview," European Journal of Operational Research, Elsevier, vol. 235(3), pages 471-483.
    12. Long He & Ho-Yin Mak & Ying Rong & Zuo-Jun Max Shen, 2017. "Service Region Design for Urban Electric Vehicle Sharing Systems," Manufacturing & Service Operations Management, INFORMS, vol. 19(2), pages 309-327, May.
    13. Alireza Ghahtarani & Ahmed Saif & Alireza Ghasemi, 2022. "Robust portfolio selection problems: a comprehensive review," Operational Research, Springer, vol. 22(4), pages 3203-3264, September.
    14. Huan Xu & Constantine Caramanis & Shie Mannor, 2012. "Optimization Under Probabilistic Envelope Constraints," Operations Research, INFORMS, vol. 60(3), pages 682-699, June.
    15. Huan Xu & Constantine Caramanis & Shie Mannor, 2012. "A Distributional Interpretation of Robust Optimization," Mathematics of Operations Research, INFORMS, vol. 37(1), pages 95-110, February.
    16. 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.
    17. Wei Liu & Li Yang & Bo Yu, 2021. "KDE distributionally robust portfolio optimization with higher moment coherent risk," Annals of Operations Research, Springer, vol. 307(1), pages 363-397, December.
    18. Zhi Chen & Weijun Xie, 2021. "Regret in the Newsvendor Model with Demand and Yield Randomness," Production and Operations Management, Production and Operations Management Society, vol. 30(11), pages 4176-4197, November.
    19. Alireza Ghahtarani & Ahmed Saif & Alireza Ghasemi, 2021. "Robust Portfolio Selection Problems: A Comprehensive Review," Papers 2103.13806, arXiv.org, revised Jan 2022.
    20. 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.

    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:60:y:2012:i:1:p:150-162. 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.