Robust optimization

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 violations, while keeping the problem tractable. Specifically, for LP, MIP, SOCP, SDP, our approaches retain the same complexity class as the original model. The robust QCQP becomes a SOCP, which is computationally as attractive as the nominal problem. In network flows, we propose an algorithm for solving the robust minimum cost flow problem in polynomial number of nominal minimum cost flow problems in a modified network. For 0 - 1 discrete optimization problem with cost uncertainty, the robust counterpart of a polynomially solvable 0 - 1 discrete optimization problem remains polynomially solvable and the robust counterpart of an NP-hard o-approximable 0-1 discrete optimization problem, remains a-approximable.

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2004

Author dc:creator

• Sim, Melvyn

Advisor dc:contributor.advisor

• Dimitris J. Bertsimas.

• Operations Research Center.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/17725

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/17725