Finite Adaptability in Multistage Linear Optimization
Authors:
- 6 May 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 55 (12) , 2751-2766
Abstract
In multistage problems, decisions are implemented sequentially, and thus may depend on past realizations of the uncertainty. Examples of such problems abound in applications of stochastic control and operations research; yet, where robust optimization has made great progress in providing a tractable formulation for a broad class of single-stage optimization problems with uncertainty, multistage problems present significant tractability challenges. In this paper we consider an adaptability model designed with discrete second stage variables in mind. We propose a hierarchy of increasing adaptability that bridges the gap between the static robust formulation, and the fully adaptable formulation. We study the geometry, complexity, formulations, algorithms, examples and computational results for finite adaptability. In contrast to the model of affine adaptability proposed in, our proposed framework can accommodate discrete variables. In terms of performance for continuous linear optimization, the two frameworks are complementary, in the sense that we provide examples that the proposed framework provides stronger solutions and vice versa. We prove a positive tractability result in the regime where we expect finite adaptability to perform well, and illustrate this claim with an application to Air Traffic Control.Keywords
This publication has 16 references indexed in Scilit:
- A Robust Optimization Perspective on Stochastic ProgrammingOperations Research, 2007
- On Complexity of Stochastic Programming Problems2006
- On complexity of multistage stochastic programsOperations Research Letters, 2006
- Adjustable robust solutions of uncertain linear programsMathematical Programming, 2004
- The Price of RobustnessOperations Research, 2004
- Robust discrete optimization and network flowsMathematical Programming, 2003
- Robust solutions of Linear Programming problems contaminated with uncertain dataMathematical Programming, 2000
- Robust Solutions to Uncertain Semidefinite ProgramsSIAM Journal on Optimization, 1998
- A reformulation-convexification approach for solving nonconvex quadratic programming problemsJournal of Global Optimization, 1995
- A new reformulation-linearization technique for bilinear programming problemsJournal of Global Optimization, 1992