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

[摘要] The unifying theme of this dissertation is robust optimization; the study of solvingcertain types of convex robust optimization problems and the study of boundson the distance to ill-posedness for certain types of robust optimization problems.Robust optimization has recently emerged as a new modeling paradigm designedto address data uncertainty in mathematical programming problems by finding anoptimal solution for the worst-case instances of unknown, but bounded, parameters.Parameters in practical problems are not known exactly for many reasons: measurementerrors, round-off computational errors, even forecasting errors, which createda need for a robust approach. The advantages of robust optimization are two-fold:guaranteed feasible solutions against the considered data instances and not requiringthe exact knowledge of the underlying probability distribution, which are limitationsof 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 methodfor solving convex adjustable robust optimization problems and providing preliminaryresults for determining the relationship between the conditioning of a robustlinear program under structured transformations and the conditioning of the equivalentsecond-order cone program under structured perturbations. The proposed algorithmis based on Kelley;;s method and is discussed in two contexts: a general convexoptimization problem and a robust linear optimization problem with recourse underright-hand side uncertainty. The proposed algorithm is then tested on two differentrobust linear optimization problems with recourse: a newsvendor problem withsimple recourse and a production planning problem with general recourse, both underright-hand side uncertainty. Computational results and analyses are provided.Lastly, we provide bounds on the distance to infeasibility for a second-order cone programthat is equivalent to a robust counterpart under ellipsoidal uncertainty in termsof quantities involving the data defining the ellipsoid in the robust counterpart.

[发布机构] University of Michigan

[效力级别] Industrial and Operations Engineering

[关键词] Robust Linear Optimization With Recourse;Industrial and Operations Engineering;Engineering;Industrial & Operations Engineering