Robust combinatorial optimization

Dimitris Bertsimas


April 3,
refreshments at 3:45pm


We propose an approach to address data uncertainty for discrete optimization problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows to control the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0-1 discrete optimization problem on n variables, then we solve the robust counterpart by solving n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0-1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. Moreover, we show that the robust counterpart of an NP-hard $\alpha$-approximable 0-1 discrete optimization problem, remains $\alpha$-approximable. (joint work with Melvyn Sim)

Speaker's Contact Info: dbertsim(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on March 12, 2002 at 11:32 AM. Copyright © 1998-99, Sara C. Billey. All rights reserved.