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.