Optimization Online


Piecewise static policies for two-stage adjustable robust linear optimization problems under uncertainty

Omar El Housni(oe2148***at***columbia.edu)
Vineet Goyal(vg2277***at***columbia.edu)

Abstract: In this paper, we consider two-stage adjustable robust linear optimization problems under uncertain constraints and study the performance of piecewise static policies. These are a generalization of static policies where we divide the uncertainty set into several pieces and specify a static solution for each piece. We show that in general there is no piecewise static policy with a polynomial number of pieces that has a significantly better performance than an optimal static policy. This is quite surprising as piecewise static policies are significantly more general than static policies. The proof is based on a combinatorial argument and the structure of piecewise static policies.

Keywords: Robust Optimization, Adaptive Optimization, Piecewise Static Policies

Category 1: Robust Optimization


Download: [PDF]

Entry Submitted: 11/30/2015
Entry Accepted: 11/30/2015
Entry Last Modified: 11/30/2015

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