Robust Linear Optimization With Recourse

Abstract

We propose an approach to two-stage linear optimization with recourse that does not involve 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 uncertain parameters as belonging to a polyhedral uncertainty set and minimize the sum of the rst-stage costs and the worst-case second-stage costs over that set, i.e., taking a robust optimization 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 examples 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.