Journal
SIAM JOURNAL ON OPTIMIZATION
Volume 32, Issue 4, Pages 2828-2858Publisher
SIAM PUBLICATIONS
DOI: 10.1137/21M1442504
Keywords
probability bounds; combinatorial optimization; PERT
Categories
Funding
- MOE Academic Research [T2MOE1906]
- Engineering Systems and Design, Singapore University of Technology and Design, Singapore
Ask authors/readers for more resources
In this paper, the tightest possible bounds on the probability of the optimal value of a combinatorial optimization problem exceeding a given number are computed based on the marginal distributions of the objective. The complexity of computing the bounds is analyzed, and instances where the bounds can be computed in polynomial time are identified. The results complement existing results for computing the probability with independent random variables.
In this paper, we compute the tightest possible bounds on the probability that the optimal value of a combinatorial optimization problem in maximization form with a random objective exceeds a given number, assuming only knowledge of the marginal distributions of the objective coefficient vector. The bounds are ``extremal' since they are valid across all joint distributions with the given marginals. We analyze the complexity of computing the bounds, assuming discrete marginals, and identify instances when the bounds are computable in polynomial time. For compact 0/1 V-polytopes, we show that the tightest upper bound is weakly NP-hard to compute by providing a pseudopolynomial time algorithm. On the other hand, the tightest lower bound is shown to be strongly NP-hard to compute for compact 0/1 V-polytopes by restricting our attention to Bernoulli random variables. For compact 0/1 H-polytopes, for the special case of PERT networks arising in project management, we show that the tightest upper bound is weakly NP-hard to compute by providing a pseudopolynomial time algorithm. The results in the paper complement existing results in the literature for computing the probability with independent random variables.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available