Optimization Online


A constraint sampling approach for multi-stage robust optimization

Phebe Vayanos(fpv02***at***imperial.ac.uk)
Daniel Kuhn(d.kuhn***at***imperial.ac.uk)
Berc Rustem(br***at***doc.ic.ac.uk)

Abstract: We propose a tractable approximation scheme for convex (not necessarily linear) multi-stage robust optimization problems. We approximate the adaptive decisions by finite linear combinations of prescribed basis functions and demonstrate how one can optimize over these decision rules at low computational cost through constraint randomization. We obtain a-priori probabilistic guarantees on the feasibility properties of the optimal decision rule by extending existing constraint sampling techniques from the single- to the multi-stage case. We demonstrate that for a suitable choice of basis functions, the approximation converges as the size of the basis and the number of sampled constraints tend to infinity. The approach yields an algorithm parameterized in the basis size, the probability of constraint violation and the confidence that this probability will not be exceeded. These three parameters serve to tune the trade-off between optimality and feasibility of the decision rules and the computational cost of the algorithm. We assess the convergence and scalability properties of our approach in the context of two inventory management problems.

Keywords: multi-stage robust optimization, decision rules, scenario approximation, violation probability

Category 1: Robust Optimization

Citation: Working paper, Department of Computing, Imperial College London, November 2010

Download: [PDF]

Entry Submitted: 11/26/2010
Entry Accepted: 11/26/2010
Entry Last Modified: 11/26/2010

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 Programming Society