Optimization Online


Distributionally Robust Optimization and its Tractable Approximations

Joel Goh (joelgoh***at***nus.edu.sg)
Melvyn Sim (dscsimm***at***nus.edu.sg)

Abstract: In this paper, we focus on a linear optimization problem with uncertainties, having expectations in the objective and in the set of constraints. We present a modular framework to obtain an approximate solution to the problem that is distributionally robust, and more flexible than the standard technique of using linear rules. Our framework begins by firstly affinely-extending the set of primitive uncertainties to generate new linear decision rules of larger dimensions, and are therefore more flexible. Next, we develop new piecewise-linear decision rules which allow a more flexible re-formulation of the original problem. The reformulated problem will generally contain terms with expectations on the positive parts of the recourse variables. Finally, we convert the uncertain linear program into a deterministic convex program by constructing distributionally robust bounds on these expectations. These bounds are constructed by first using different pieces of information on the distribution of the underlying uncertainties to develop separate bounds, and next integrating them into a combined bound that is better than each of the individual bounds. We present an example illustrating how our framework can be applied to robustly optimize a multi-period inventory management problem with fill-rate constraints.

Keywords: Robust Optimization, Stochastic Programming

Category 1: Robust Optimization

Citation: Working paper, NUS Business School

Download: [PDF]

Entry Submitted: 04/20/2009
Entry Accepted: 04/20/2009
Entry Last Modified: 08/04/2009

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