We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

On the Power of Affine Policies in Dynamic Optimization

Formal Metadata

Title
On the Power of Affine Policies in Dynamic Optimization
Alternative Title
On the Power of Affine Policies in Two-Stage Adjustable Robust Optimization
Title of Series
Number of Parts
39
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
Affine policies are widely used as a solution approach in dynamic optimization where computing an optimal adjustable solution is usually intractable. While the worst case performance of affine policies can be significantly bad, the empirical performance is observed to be near-optimal for a large class of problem instances. For instance, in the two-stage dynamic robust optimization problem with linear covering constraints and uncertain right hand side, the worst-case approximation bound for affine policies is O(√m) that is also tight (see Bertsimas and Goyal [8]), whereas observed empirical performance is near-optimal. This work aims to address this stark-contrast between the worst-case and the empirical performance of affine policies. We show that affine policies are provably a good approximation for the two-stage adjustable robust optimization problem with high probability on random instances where the constraint coefficients are generated i.i.d. from a large class of distributions; thereby, providing a theoretical justification of the observed empirical performance. We also consider the performance of affine policies for an important class of uncertainty sets, namely the budget of uncertainty and intersection of budget of uncertainty sets. We show that surprisingly affine policies provide nearly the best possible approximation for this class of uncertainty sets that matches the hardness of approximation; thereby, further confirming the power of affine policies. This talk is based is joint work with my student Omar El Housni.