Open Collections

Analyzing Policies in Dynamic Robust Optimization

Banff International Research Station for Mathematical Innovation and Discovery

Determining optimal policies in dynamic robust optimization is often challenging due to the curse of dimensionality. As a result, many researchers have proposed restricting attention to classes of simpler decision rules (for instance, static or affine), which are computationally tractable and often deliver excellent performance. In this work, we propose a general theory for analyzing the effectiveness of policies in a large class of dynamic robust optimization problems. Through a transformation of the objective function, we provide a geometric characterization for the effectiveness of a policy class, which is helpful in either establishing the policyâ s optimality or bounding its sub-optimality gap. Based on this geometric characterization, we recover and generalize several different results on static and affine polices from the literature. Furthermore, our theory establishes interesting connections with the theory of discrete convexity, global concave envelopes, and the integrality gap of mixed integer linear programs.

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

video/mp4

Author affiliation: Boston College

2019-07-14

Attribution-NonCommercial-NoDerivatives 4.0 International

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

Unreviewed

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