ON CAPACITATED STOCHASTIC CHAIN PROBLEMS IN A NETWORK

This paper considers two basic problems relating to capacitated chains in a stochastic network in which each are has a discrete arbitrary pr obability distribution for its capacity. Given a source-sink pair, the first problem is to find an optimal capacity chain subject to a chanc e constraint. By treating the right-hand side of the chance constraint also as a decision variable, the complete spectrum of optimal solutio ns is found by a polynomial algorithm. The second problem is to find a chain with the highest expected capacity. A vectorial labeling algori thm which exploits a certain dominance property and an effective bound is presented for solving this problem. Both are illustrated by an exa mple, and computational results on the second are included. (C) 1998 J ohn Wiley & Sons, Inc.