On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems
We consider a two-stage mixed integer stochastic optimization problem and show that a static robust solution is a good approximation to the fully adaptable two-stage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In parti...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute for Operations Research and the Management Sciences
2012
|
| Online Access: | http://hdl.handle.net/1721.1/69831 https://orcid.org/0000-0002-1985-1003 |
| _version_ | 1826196358042746880 |
|---|---|
| author | Goyal, Vineet Bertsimas, Dimitris J |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Goyal, Vineet Bertsimas, Dimitris J |
| author_sort | Goyal, Vineet |
| collection | MIT |
| description | We consider a two-stage mixed integer stochastic optimization problem and show that a static robust solution is a good approximation to the fully adaptable two-stage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, we show that if the right-hand side of the constraints is uncertain and belongs to a symmetric uncertainty set (such as hypercube, ellipsoid or norm ball) and the probability measure is also symmetric, then the cost of the optimal fixed solution to the corresponding robust problem is at most twice the optimal expected cost of the two-stage stochastic problem. Furthermore, we show that the bound is tight for symmetric uncertainty sets and can be arbitrarily large if the uncertainty set is not symmetric. We refer to the ratio of the optimal cost of the robust problem and the optimal cost of the two-stage stochastic problem as the stochasticity gap. We also extend the bound on the stochasticity gap for another class of uncertainty sets referred to as positive.
If both the objective coefficients and right-hand side are uncertain, we show that the stochasticity gap can be arbitrarily large even if the uncertainty set and the probability measure are both symmetric. However, we prove that the adaptability gap (ratio of optimal cost of the robust problem and the optimal cost of a two-stage fully adaptable problem) is at most four even if both the objective coefficients and the right-hand side of the constraints are uncertain and belong to a symmetric uncertainty set. The bound holds for the class of positive uncertainty sets as well. Moreover, if the uncertainty set is a hypercube (special case of a symmetric set), the adaptability gap is one under an even more general model of uncertainty where the constraint coefficients are also uncertain. |
| first_indexed | 2024-09-23T10:25:19Z |
| format | Article |
| id | mit-1721.1/69831 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:25:19Z |
| publishDate | 2012 |
| publisher | Institute for Operations Research and the Management Sciences |
| record_format | dspace |
| spelling | mit-1721.1/698312023-03-01T02:08:27Z On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems Goyal, Vineet Bertsimas, Dimitris J Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Bertsimas, Dimitris J. Goyal, Vineet Bertsimas, Dimitris J. We consider a two-stage mixed integer stochastic optimization problem and show that a static robust solution is a good approximation to the fully adaptable two-stage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, we show that if the right-hand side of the constraints is uncertain and belongs to a symmetric uncertainty set (such as hypercube, ellipsoid or norm ball) and the probability measure is also symmetric, then the cost of the optimal fixed solution to the corresponding robust problem is at most twice the optimal expected cost of the two-stage stochastic problem. Furthermore, we show that the bound is tight for symmetric uncertainty sets and can be arbitrarily large if the uncertainty set is not symmetric. We refer to the ratio of the optimal cost of the robust problem and the optimal cost of the two-stage stochastic problem as the stochasticity gap. We also extend the bound on the stochasticity gap for another class of uncertainty sets referred to as positive. If both the objective coefficients and right-hand side are uncertain, we show that the stochasticity gap can be arbitrarily large even if the uncertainty set and the probability measure are both symmetric. However, we prove that the adaptability gap (ratio of optimal cost of the robust problem and the optimal cost of a two-stage fully adaptable problem) is at most four even if both the objective coefficients and the right-hand side of the constraints are uncertain and belong to a symmetric uncertainty set. The bound holds for the class of positive uncertainty sets as well. Moreover, if the uncertainty set is a hypercube (special case of a symmetric set), the adaptability gap is one under an even more general model of uncertainty where the constraint coefficients are also uncertain. National Science Foundation (U.S.) (NSF Grant DMI-0556106) National Science Foundation (U.S.) (NSF Grant EFRI-0735905) 2012-03-22T15:29:46Z 2012-03-22T15:29:46Z 2010-05 2009-12 Article http://purl.org/eprint/type/JournalArticle 0364-765X 1526-5471 http://hdl.handle.net/1721.1/69831 Bertsimas, D., and V. Goyal. “On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems.” Mathematics of Operations Research 35.2 (2010): 284–305. https://orcid.org/0000-0002-1985-1003 en_US http://dx.doi.org/10.1287/moor.1090.0440 Mathematics of Operations Research Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute for Operations Research and the Management Sciences Prof. Bertsimas via Alex Caracuzzo |
| spellingShingle | Goyal, Vineet Bertsimas, Dimitris J On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems |
| title | On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems |
| title_full | On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems |
| title_fullStr | On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems |
| title_full_unstemmed | On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems |
| title_short | On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems |
| title_sort | on the power of robust solutions in two stage stochastic and adaptive optimization problems |
| url | http://hdl.handle.net/1721.1/69831 https://orcid.org/0000-0002-1985-1003 |
| work_keys_str_mv | AT goyalvineet onthepowerofrobustsolutionsintwostagestochasticandadaptiveoptimizationproblems AT bertsimasdimitrisj onthepowerofrobustsolutionsintwostagestochasticandadaptiveoptimizationproblems |