Robust Linear Optimization With Recourse

We propose an approach to two-stage linear optimization with recourse that does not in-volve a probabilistic description of the uncertainty and allows the decision-maker to adjust the degree of conservativeness of the model, while preserving its linear properties. We model un-certain parameters as 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, i.e., taking a robust opti-mization approach. 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 uncertain parameters. We establish that the robust problem is a linear programming problem with a potentially very large number of constraints, and describe how a cutting plane algorithm can be used in the the two-stage setting. We test the robust modeling approach on two ex-amples of problems, one with simple, and one with general recourse, to illustrate the structure and performance of robust policies as well as to evaluate the performance of the cutting plane algorithm