Premium
On capacitated stochastic chain problems in a network
Author(s) -
Ganapathy L.,
Nair K. P. K.
Publication year - 1998
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199801)31:1<19::aid-net3>3.0.co;2-n
Subject(s) - mathematical optimization , constraint (computer aided design) , stochastic dominance , computer science , mathematics , random variable , statistics , geometry
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 for solving this problem. Both are illustrated by an example, and computational results on the second are included. © 1998 John Wiley & Sons, Inc. Networks 31: 19–27, 1998