Open Collections

On the Optimality of Affine Policies for Budgeted Uncertainty Sets

Banff International Research Station for Mathematical Innovation and Discovery

We study the performance of affine policies for two-stage adjustable robust optimization problem under a budget of uncertainty set. This important class of uncertainty sets provides the flexibility to adjust the level of conservatism in terms of probabilistic bounds on constraint violations. The two-stage adjustable robust optimization problem is hard to approximate within a factor better than $\Omega( \frac{\log n}{\log \log n})$ for budget of uncertainty sets where $n$ is the number of decision variables. We show that surprisingly affine policies provide the optimal approximation for this class of uncertainty sets that matches the hardness of approximation; thereby, further confirming the power of affine policies. We also present strong theoretical guarantees for affine policies when the uncertainty set is given by intersection of budget constraints. Furthermore, our analysis gives a significantly faster algorithm to compute near-optimal affine policies. This is joint work with Vineet Goyal.

Mathematics; Operations research, mathematical programming; Computer science; Applied computer science

video/mp4

Author affiliation: Columbia University

2019-07-15

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/70979

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/