A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization
In this paper, we study the performance of static solutions for two-stage adjustable robust linear optimization problems with uncertain constraint and objective coefficients and give a tight characterization of the adaptivity gap. Computing an optimal adjustable robust optimization problem is often...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2016
|
| Online Access: | http://hdl.handle.net/1721.1/103403 https://orcid.org/0000-0002-1985-1003 |
| _version_ | 1811086776728551424 |
|---|---|
| author | Goyal, Vineet Lu, Brian Y. Bertsimas, Dimitris J Bertsimas, Dimitris J. |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Goyal, Vineet Lu, Brian Y. Bertsimas, Dimitris J Bertsimas, Dimitris J. |
| author_sort | Goyal, Vineet |
| collection | MIT |
| description | In this paper, we study the performance of static solutions for two-stage adjustable robust linear optimization problems with uncertain constraint and objective coefficients and give a tight characterization of the adaptivity gap. Computing an optimal adjustable robust optimization problem is often intractable since it requires to compute a solution for all possible realizations of uncertain parameters (Feige et al. in Lect Notes Comput Sci 4513:439–453, 2007). On the other hand, a static solution is a single (here and now) solution that is feasible for all possible realizations of the uncertain parameters and can be computed efficiently for most dynamic optimization problems. We show that for a fairly general class of uncertainty sets, a static solution is optimal for the two-stage adjustable robust linear packing problems. This is highly surprising in view of the usual perception about the conservativeness of static solutions. Furthermore, when a static solution is not optimal for the adjustable robust problem, we give a tight approximation bound on the performance of the static solution that is related to a measure of non-convexity of a transformation of the uncertainty set. We also show that our bound is at least as good (and in many case significantly better) as the bound given by the symmetry of the uncertainty set (Bertsimas and Goyal in Math Methods Oper Res 77(3):323–343, 2013; Bertsimas et al. in Math Oper Res 36(1):24–54, 2011). |
| first_indexed | 2024-09-23T13:34:34Z |
| format | Article |
| id | mit-1721.1/103403 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:34:34Z |
| publishDate | 2016 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1034032022-10-01T15:48:02Z A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization Goyal, Vineet Lu, Brian Y. Bertsimas, Dimitris J Bertsimas, Dimitris J. Sloan School of Management Bertsimas, Dimitris J. In this paper, we study the performance of static solutions for two-stage adjustable robust linear optimization problems with uncertain constraint and objective coefficients and give a tight characterization of the adaptivity gap. Computing an optimal adjustable robust optimization problem is often intractable since it requires to compute a solution for all possible realizations of uncertain parameters (Feige et al. in Lect Notes Comput Sci 4513:439–453, 2007). On the other hand, a static solution is a single (here and now) solution that is feasible for all possible realizations of the uncertain parameters and can be computed efficiently for most dynamic optimization problems. We show that for a fairly general class of uncertainty sets, a static solution is optimal for the two-stage adjustable robust linear packing problems. This is highly surprising in view of the usual perception about the conservativeness of static solutions. Furthermore, when a static solution is not optimal for the adjustable robust problem, we give a tight approximation bound on the performance of the static solution that is related to a measure of non-convexity of a transformation of the uncertainty set. We also show that our bound is at least as good (and in many case significantly better) as the bound given by the symmetry of the uncertainty set (Bertsimas and Goyal in Math Methods Oper Res 77(3):323–343, 2013; Bertsimas et al. in Math Oper Res 36(1):24–54, 2011). 2016-06-30T20:38:29Z 2016-06-30T20:38:29Z 2014-04 2013-01 2016-05-23T12:11:03Z Article http://purl.org/eprint/type/JournalArticle 0025-5610 1436-4646 http://hdl.handle.net/1721.1/103403 Bertsimas, Dimitris, Vineet Goyal, and Brian Y. Lu. “A Tight Characterization of the Performance of Static Solutions in Two-Stage Adjustable Robust Linear Optimization.” Mathematical Programming 150.2 (2015): 281–319. https://orcid.org/0000-0002-1985-1003 en http://dx.doi.org/10.1007/s10107-014-0768-y Mathematical Programming Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Goyal, Vineet Lu, Brian Y. Bertsimas, Dimitris J Bertsimas, Dimitris J. A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization |
| title | A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization |
| title_full | A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization |
| title_fullStr | A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization |
| title_full_unstemmed | A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization |
| title_short | A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization |
| title_sort | tight characterization of the performance of static solutions in two stage adjustable robust linear optimization |
| url | http://hdl.handle.net/1721.1/103403 https://orcid.org/0000-0002-1985-1003 |
| work_keys_str_mv | AT goyalvineet atightcharacterizationoftheperformanceofstaticsolutionsintwostageadjustablerobustlinearoptimization AT lubriany atightcharacterizationoftheperformanceofstaticsolutionsintwostageadjustablerobustlinearoptimization AT bertsimasdimitrisj atightcharacterizationoftheperformanceofstaticsolutionsintwostageadjustablerobustlinearoptimization AT bertsimasdimitrisj atightcharacterizationoftheperformanceofstaticsolutionsintwostageadjustablerobustlinearoptimization AT goyalvineet tightcharacterizationoftheperformanceofstaticsolutionsintwostageadjustablerobustlinearoptimization AT lubriany tightcharacterizationoftheperformanceofstaticsolutionsintwostageadjustablerobustlinearoptimization AT bertsimasdimitrisj tightcharacterizationoftheperformanceofstaticsolutionsintwostageadjustablerobustlinearoptimization AT bertsimasdimitrisj tightcharacterizationoftheperformanceofstaticsolutionsintwostageadjustablerobustlinearoptimization |