Robust combinatorial optimization
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
optimization problem, remains $\alpha$-approximable.
(joint work with Melvyn Sim)
Speaker's Contact Info: dbertsim(at-sign)mit.edu
Return to seminar home page
Page loaded on March 12, 2002 at 11:32 AM.
Copyright © 1998-99, Sara C. Billey.
All rights reserved.