Stochastic bounds on distributions of optimal value functions with applications to PERT, network flows and realiability.

*(English)*Zbl 0609.90093In many classical combinatorial optimization problems, including critical and shortest paths, maximum flow, and network reliability, the introduction of uncertainty considerably complicates the calculation of system performance. In fact, in these contexts, computing system performance exactly can often be an impossible task. Therefore, obtaining (stochastic) bounds on the system’s performance becomes an attractive and useful alternative. This paper studies several stochastic bounds that are applicable to these contexts and to a broader set of problems that can be described by the general combinatorial concepts of clutters and blocking clutters. We begin our discussion by defining these unifying concepts and illustrating their specialization in several problem contexts.

##### MSC:

90C27 | Combinatorial optimization |

90C15 | Stochastic programming |

90B25 | Reliability, availability, maintenance, inspection in operations research |

90B10 | Deterministic network models in operations research |

90B35 | Deterministic scheduling theory in operations research |