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 arc has a discrete arbitrary probability distribution for its capacity. Given a source–sink pair, the first problem is to find an optimal capacity chain subject to a chance constraint. By treating the right-hand side of the chance constraint also as a decision variable, the complete spectrum of optimal solutions is found by a polynomial algorithm. The second problem is to find a chain with the highest expected capacity. A vectorial labeling algorithm which exploits a certain dominance property and an effective bound is presented by solving this problem. Both are illustrated by an example, and computational results on the second are included.