Discrete Optimization Under Moment Uncertainty: Complexity, Persistency and Asymptotics

Friday, January 19, 2007 - 11:00am - 11:50am
EE/CS 3-180
Dimitris Bertsimas (Massachusetts Institute of Technology)
We address the problem of evaluating the expected optimal objective
value of a discrete optimization problem under uncertainty in the objective
coefficients. The probabilistic model we consider prescribes limited marginal
distributional information for the objective coefficients in the form of
moments. We show that for a fairly general class of marginal information,
a tight upper (lower) bound on the expected optimal objective value of
a discrete maximization (minimization) problem can be computed in
polynomial time if the corresponding deterministic discrete
optimization problem is solvable
in polynomial time. We provide an efficiently solvable semidefinite
programming formulation to compute this tight bound.
We use the insights from this analysis to:
a) understand the
percistency of a decision variable, i.e.,
the probability that
it is part of an optimal solution;
for instance, in project scheduling, when the task activity times are
random, the challenge is to determine a set of critical activities
that will potentially lie on the longest path;
b) to analyze the
asymptotic behavior of a general class of combinatorial problems that includes
the linear assignment, spanning tree and traveling salesman problems, under
knowledge of complete marginal distributions, with and without
independence. We calculate the limiting constants exactly.
(joint work with Karthik Natarajan and Chung Piaw Teo)