Optimization Online


Robust Linear Optimization With Recourse

Aurelie Thiele (aurelie.thiele***at***lehigh.edu)
Tara Terry (tlterry***at***umich.edu)
Marina Epelman (mepelman***at***umich.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

  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