Hibye

Robust Optimization

by

Melvyn Sim

B.Eng, Electrical Engineering, National Univerity of Singapore (1995) M.Eng, Electrical Engineering, National Univerity of Singapore (1996) S.M, HPCES, Singapore-MIT-Alliance (2000) Submitted to the Sloan School of Management in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Operations Research at the MASSACHUSETTS INSTITUTE OF TECHNOLOGY June 2004 c Massachusetts Institute of Technology 2004. All rights reserved.

Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sloan School of Management May 14, 2004 Certified by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dimitris J. Bertsimas Boeing Professor of Operations Research Sloan School of Management Thesis Supervisor Accepted by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . James B. Orlin Edward Pennell Brooks Professor of Operations Research Co-Director, Operations Research Center

2

Robust Optimization by Melvyn Sim

Submitted to the Sloan School of Management on May 14, 2004, in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Operations Research

Abstract

We propose new methodologies in robust optimization that promise greater tractability, both theoretically and practically than the classical robust framework. We cover a broad range of mathematical optimization problems, including linear optimization (LP), quadratic constrained quadratic optimization (QCQP), general conic optimization including second order cone programming (SOCP) and semidefinite optimization (SDP), mixed integer optimization (MIP), network flows and 0 − 1 discrete optimization. Our approach allows the modeler to vary the level of conservatism of the robust solutions in terms of probabilistic bounds of constraint...