Given a combinatorial optimization problem with an arbitrary partition of random objective coefficients, we evaluate the tightest possible bound on the expected optimal value over all joint distributions consistent with the given multivariate marginals of the elements in the partition. We discuss the computational tractability of the evaluation of the tight bound and the construction of the extremal distributions that achieve the bound. We apply the proposed model for PERT networks to evaluate the bounds for project tardiness and show that the minimax two-stage project crashing problem under the discrete multivariate marginal assumption is tractable. This is joint work with Karthik Natarajan and it was partly done when the author was in the Operations Research Center at MIT.
Copyright. All Rights Reserved.