Robust linear optimization using distributional information

Robust optimization is a methodology for dealing with optimization problems with data uncertainty. The classical robust optimization approach aims to find a solution that is protected against infeasibility. When applications can tolerate a small chance of infeasibility, however, solutions from this approach tend to be too conservative. For this class of applications, methods that produce less conservative solutions with certain probabilistic guarantees of feasibility could prove to be useful. Developing such a method is the main focus of this dissertation.; The dissertation considers a linear programming problem in which the constraint matrix is subject to uncertainty. In particular, each uncertain element of the matrix is modeled as a random variable with a bounded support. To obtain a less conservative solution of the problem, an optimization formulation is constructed based on the parameters that restrict the variability of the uncertain elements. By construction, an optimal solution of the formulation may become infeasible by violating the constraints of the problem. Exploiting distributional information on the uncertain elements, several upper bounds on the constraint violation probability are established. In addition to the case of full distributional information, the case of limited distributional information in the form of the first and second moments or samples is considered. When the range of each uncertain element is symmetrically bounded around its mean, it is shown that the bounds developed here are stronger than one in the literature which does not use distributional information. Obtaining stronger bounds is important because they lead to a more cost-effective solution under the same probabilistic guarantee of feasibility.; A discrete-time stochastic inventory control problem with quality of service constraints is considered as an application. Numerical tests verify the effectiveness of the robust optimization with distributional information by showing that cost savings amount to 36%-54%. Finally, the philosophy of robust optimization is extended to an infinite horizon discounted cost Markov decision problem where uncertainty resides in the transition probabilities. The requisite theory is developed and benefits of the robust approach with distributional information are also observed through a numerical example.