# 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)

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)