Optimization Online


On the Complexity of Non-Overlapping Multivariate Marginal Bounds for Probabilistic Combinatorial Optimization Problems

Karthik Natarajan (knataraj***at***cityu.edu.hk)
Xuan Vinh Doan (vanxuan***at***uwaterloo.ca)

Abstract: Given a combinatorial optimization problem with an arbitrary partition of the set of random objective coefficients, we evaluate the tightest possible bound on the expected optimal value for joint distributions consistent with the given multivariate marginals of the subsets in the partition. For univariate marginals, this bound was first proposed by Meilijson and Nadas (Journal of Applied Probability, 1979). We generalize the bound to non-overlapping multivariate marginals using multiple choice integer programming. For discrete distributions, new instances of polynomial time computable multivariate marginal bounds are identified. For the problem of selecting up to $M$ items out a set of $N$ items of maximum total weight, the bound is shown to be computable in polynomial time, when the size of each subset in the partition is $\mathrm{O}(\log N)$. For an activity-on-arc PERT network, the partition is naturally defined by subsets of incoming arcs into nodes. The worst-case expected project duration is shown to be computable in time polynomial in the maximum number of scenarios for any subset and the size of the network. An instance of a polynomial time solvable two stage stochastic program arising from project crashing is identified. An important feature of the bound is that it is exactly achievable by a joint distribution, unlike many of the existing bounds.

Keywords: PERT, Probability Distributions, Stochastic Programming

Category 1: Combinatorial Optimization

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 10/05/2010
Entry Accepted: 10/06/2010
Entry Last Modified: 03/06/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society