Obtaining risk-averse solutions in optimization problems with uncertain objective

Abstract

In classical optimization problems, parameters are assumed to be fixed. However, most of the real life problems involve uncertainty. In such cases, classical optimization models may be used by fixing the uncertain coefficients with their mean or median value. However, such models are likely to give solutions that have unwanted objective value, or even worse, be infeasible for the true parameter value. In this thesis, we study methods to find risk-averse solutions for optimization problems with objective function uncertainty. First, we look in to the cardinality constrained approach, which is commonly used in robust optimization. When applied to uncertain constraint coefficients, cardinality constrained uncertainty has advantages in that the robust model can be formulated as a linear model as long as the underlying problem is linear, and it provides theoretical upper bound on probability of its solution being infeasible. However, when applied to uncertain objective coefficients, some of the properties no longer hold and raises other issues like inconsistency of its solutions. We discuss the cause of the issues and state the necessary and sufficient condition to avoid one of the issues. We also suggest a new robust model that does not suffer from the issues, while preserving the merits of using the cardinality constrained uncertainty. Secondly, we look into the method of using the weighted OWA (WOWA) criterion to two-stage problems as a means to obtain risk-averse robust solutions. The weighted OWA is a function that aggregates a set of values with weights assigned based on the rank and relative importance of each value. We apply the WOWA criterion to two-stage problems, and present decomposition algorithms to solve them. The algorithms are applied to a location-transportation problem with uncertain demands and computational results are presented. Finally, we propose a new risk measure: weighted averaging of quantiles of expectation (WAQE), an extension of widely used conditional value at risk (CVaR). Under certain assumptions, WAQE is a coherent risk measure and it has close relation with weighted OWA when applied to discrete random variable. We show that a discrete random variable that minimizes WAQE with certain conditions is second order stochastic dominant. Also, we propose a delayed cut generation algorithm that minimizes WAQE in an optimization problem and test its computational performance though experiments.