Optimization Online


Supermodularity and Affine Policies in Dynamic Robust Optimization

Dan Iancu(daniancu***at***stanford.edu)
Mayank Sharma(mxsharma***at***us.ibm.com)
Maxim Sviridenko(M.I.Sviridenko***at***warwick.ac.uk)

Abstract: This paper considers robust dynamic optimization problems, where the unknown parameters are modeled as uncertainty sets. We seek to bridge two classical paradigms for solving such problems, namely (1) Dynamic Programming (DP), and (2) policies parameterized in model uncertainties (also known as decision rules), obtained by solving tractable convex optimization problems. We provide a set of unifying conditions (based on the interplay between the convexity and supermodularity of the DP value functions, and the lattice structure of the uncertainty sets) that, taken together, guarantee the optimality of the class of affine decision rules. We also derive conditions under which such affine rules can be obtained by optimizing simple (e.g., linear) objective functions over the uncertainty sets. Our results suggest new modeling paradigms for dynamic robust optimization, and our proofs, which bring together ideas from three areas of optimization typically studied separately (robust optimization, combinatorial optimization - the theory of lattice programming and supermodularity, and global optimization - the theory of concave envelopes), may be of independent interest. We exemplify our findings in an application concerning the design of flexible contracts in a two-echelon supply chain, where the optimal contractual pre-commitments and the optimal ordering quantities can be found by solving a single linear program of small size.

Keywords: robust optimization, affine decision rules, supermodularity, lattice programming, concave envelopes, inventory management

Category 1: Robust Optimization

Category 2: Other Topics (Dynamic Programming )

Category 3: Combinatorial Optimization (Polyhedra )

Citation: Submitted for publication.

Download: [PDF]

Entry Submitted: 06/07/2012
Entry Accepted: 06/07/2012
Entry Last Modified: 06/07/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society