Robust Linear Optimization with Recourse: Solution Methods and Other Properties.

Abstract

The unifying theme of this dissertation is robust optimization; the study of solving certain types of convex robust optimization problems and the study of bounds on the distance to ill-posedness for certain types of robust optimization problems. Robust optimization has recently emerged as a new modeling paradigm designed to address data uncertainty in mathematical programming problems by finding an optimal solution for the worst-case instances of unknown, but bounded, parameters. Parameters in practical problems are not known exactly for many reasons: measurement errors, round-off computational errors, even forecasting errors, which created a need for a robust approach. The advantages of robust optimization are two-fold: guaranteed feasible solutions against the considered data instances and not requiring the exact knowledge of the underlying probability distribution, which are limitations of chance-constraint and stochastic programming. Adjustable robust optimization, an extension of robust optimization, aims to solve mathematical programming problems where the data is uncertain and sets of decisions can be made at different points in time, thus producing solutions that are less conservative in nature than those produced by robust optimization.

This dissertation has two main contributions: presenting a cutting-plane method for solving convex adjustable robust optimization problems and providing preliminary results for determining the relationship between the conditioning of a robust linear program under structured transformations and the conditioning of the equivalent second-order cone program under structured perturbations. The proposed algorithm is based on Kelley's method and is discussed in two contexts: a general convex optimization problem and a robust linear optimization problem with recourse under right-hand side uncertainty. The proposed algorithm is then tested on two different robust linear optimization problems with recourse: a newsvendor problem with simple recourse and a production planning problem with general recourse, both under right-hand side uncertainty. Computational results and analyses are provided. Lastly, we provide bounds on the distance to infeasibility for a second-order cone program that is equivalent to a robust counterpart under ellipsoidal uncertainty in terms of quantities involving the data defining the ellipsoid in the robust counterpart.