Tata Institute of Fundamental Research
Static vs Adjustable Solutions in Dynamic Optimization
Seminar
Speaker:
Vineet Goyal (Columbia University
Industrial Engineering and Operations Research
500 West, 120th Street
New York, NY 10027
United States of America)
Organiser:
Sandeep K Juneja
Date:
Wednesday, 28 Aug 2013, 17:00 to 18:00
Venue:
AG-69
(Scan to add to calendar)
Abstract:
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, but a static solution can be computed efficiently in most cases. We show that for a fairly general class of uncertainty sets, a static solution is optimal for the two-stage adjustable robust linear optimization problem. Furthermore, when a static solution is not optimal, 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.
| Speaker: | Vineet Goyal (Columbia University Industrial Engineering and Operations Research 500 West, 120th Street New York, NY 10027 United States of America) |
| Organiser: | Sandeep K Juneja |
| Date: | Wednesday, 28 Aug 2013, 17:00 to 18:00 |
| Venue: | AG-69 |
(Scan to add to calendar)
Abstract:
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, but a static solution can be computed efficiently in most cases. We show that for a fairly general class of uncertainty sets, a static solution is optimal for the two-stage adjustable robust linear optimization problem. Furthermore, when a static solution is not optimal, 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.