Multicommodity Network Flows with Probabilistic Losses

Abstract

This paper considers the problem of maximizing the expected value of multicommodity flows in a network in which the arcs experience probabilistic loss rates. Consideration of probabilistic losses are relevant, particularly, in communication and transportation networks. An arc-chain formulation of the problem and an efficient algorithm for computing an optimal solution are provided. The algorithm involves a modified column generation technique for identifying a constrained chain. Computational experience with the algorithm is included.