Robust Linear Optimization With Recourse

Aurelie Thiele (aurelie.thielelehigh.edu)
Tara Terry (tlterryumich.edu)
Marina Epelman (mepelmanumich.edu)

Abstract: We propose an approach to linear optimization with recourse that does not involve a probabilistic description of the uncertainty, and allows the decision-maker to adjust the degree of robustness of the model while preserving its linear properties. We model random variables as uncertain parameters belonging to a polyhedral uncertainty set and minimize the sum of the first-stage costs and the worst-case second-stage costs over that set. The decision-maker's conservatism is taken into account through a budget of uncertainty, which determines the size of the uncertainty set around the nominal values of the random variables. We establish that the robust problem is a linear programming problem with a potentially very large number of constraints, and describe how a cutting place algorithm can be used for the robust problem. Furthermore, in the case of simple recourse, we show that the robust problem can be formulated as a series of $m$ linear programming problems of size similar to the original deterministic problem, where $m$ is the number of random variables. Numerical results are encouraging.

Keywords: Robust Optimization, Cutting-plane methods, Optimization with recourse

Category 1: Robust Optimization

Category 2: Convex and Nonsmooth Optimization

Category 3: Stochastic Programming

Citation: Technical Report TR09-01, March 2009, Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI 48019

Download: [PDF]

Entry Submitted: 03/24/2009
Entry Accepted: 03/24/2009
Entry Last Modified: 05/25/2010

Modify/Update this entry