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.
Citation
Technical Report TR09-01, March 2009, Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI 48019