Supermodularity and Affine Policies in Dynamic Robust Optimization

Dan A. Iancu (), Mayank Sharma () and Maxim Sviridenko ()
Additional contact information
Dan A. Iancu: Graduate School of Business, Stanford University, Stanford, California 94305
Mayank Sharma: IBM T. J. Watson Research Center, Yorktown Heights, New York 10598
Maxim Sviridenko: Computer Science Department, University of Warwick, Coventry, CV4 7AL, United Kingdom

Operations Research, 2013, vol. 61, issue 4, 941-956

Abstract: This paper considers a particular class of dynamic robust optimization problems, where a large number of decisions must be made in the first stage, which consequently fix the constraints and cost structure underlying a one-dimensional, linear dynamical system. 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 show that if the uncertainty sets are integer sublattices of the unit hypercube, the DP value functions are convex and supermodular in the uncertain parameters, and a certain technical condition is satisfied, then decision rules that are affine in the uncertain parameters are optimal. We also derive conditions under which such rules can be obtained by optimizing simple (i.e., 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 a class of applications concerning the design of flexible production processes, where a retailer seeks to optimally compute a set of strategic decisions (before the start of a selling season), as well as in-season replenishment policies. We show that, when the costs incurred are jointly convex, replenishment policies that depend linearly on the realized demands are optimal. When the costs are also piecewise affine, all the optimal decisions can be found by solving a single linear program of small size (when all decisions are continuous) or a mixed-integer, linear program of the same size (when some strategic decisions are discrete).

Keywords: dynamic robust optimization; supermodularity; concave envelopes; lattices; Lovász extension; production planning; inventory management (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (34)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1172 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:4:p:941-956

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().