Robust Optimization: New Methodologies and Applications.

We propose new methodologies in robust optimization that are tractable and extend to a large set of uncertain optimization problems. We focus on linear programming (LP) and mixed integer programming (MIP) problems. The results are also extended to general convex optimization problems. In the first part of the thesis we focus on providing solution methods for linear optimization problems with uncertain parameters. It is well-known that the robust optimization methodology can be used to construct tractable approximations for such uncertain problems. The robust optimization based approximations available in the literature only control the probability of constraint violation, they do not control the degree of constraint violation. We propose a new formulation that allows the decision-maker to control both the probability and expected value of constraint violation. We show how to construct tractable approximations for this new formulation. The methodology can be used for both bounded and unbounded uncertain parameters. We extend the methodology to a general class of convex problems which includes second order cone programming and semi definite programming. In order to achieve this we define a new family of random variables with prescribed tail behavior. Approximations are also provided for conditional-value-at-risk constraints which in general can be hard to approximate. We apply the methodology developed in the first part of the thesis to problems in inventory management. Dynamic programming (DP) has been the leading methodology to solve these problems. DP makes it easy to determine the structure of the optimal policy by breaking the problem into smaller optimization problems. One of the major problems with the DP approach is the inability to solve these smaller problems, thereby making it impractical to determine the actual optimal policy. Dynamic programming problems can be approximately solved using sample based methods, but this requires a high number of samples in case of multi period problems. We discuss the use of expected shortfall constraints for these problems. We solve a single station single item inventory management problem but the approximations suggested can easily be extended to more complex multi echelon inventory management problems. We also solve a contract selection problem faced by a retailer when making a choice from a number of supply contracts. The retailer tries to decide an optimal set of contract terms so as to counter the demand uncertainty and reduce cost. We numerically show that the suggested methodology performs almost as good as the optimal policy determined by solving the dynamic program. We also address the problem of optimal call center design. This problem has been studied in the past using theory of dynamic control and point-wise stationary fluid approximations giving asymptotically optimal policies. We focus on the combined problem of call center design and staffing. The proposed approach takes into account the uncertainty in the incoming call volumes without making any distributional assumptions. The problems defined are computationally tractable mixed integer linear programming problems. We show that limited resource pooling is optimal when the call volumes are uncertain. We also suggest a two resource pooling heuristic for the integer program and numerically show that the heuristic is near optimal for a wide range of parameter values.