Network reliability analysis is a difficult computational problem that has attracted quite a bit of research at the interface of combinatorics, computer science and operations research. A central component of two-terminal reliability is the identification of minimum cutsets in a graph theoretic model of the underlying network. The idea is to calculate the probability that at least one path exists between some selected pair of terminal nodes through the identification of all cutsets in the corresponding graph. Since the exact calculations are intractable, bounds are calculated via identification of minimum weight cutsets.

This project will examine a network vulnerability variant of the two-terminal network reliability problem. Given a network with some small selected subset of "vulnerable" links, we would like to calculate the minimum number of network component failures that would have to occur so that all network communications involve at least one link in the vulnerable set. Students will have the opportunity to investigate several network flow models and propose combinatorial optimization algorithms based on lagrangean relaxation or other decomposition approaches. The end contribution will be to understand the mathematics behind these algorithms and to prototype one or more algorithms that can be deployed to analyze moderately sized networks in real-time.

Textbook References:

1. Michael Ball (editor), Network Models, Elsevier Amsterdam, 1995. (chapter on network reliability)
2. Rav Ahuja, James Orlin and Tom Magnanti, Network Flows, Prentice Hall New Jersey, 1993. (chapters on maximum flow and lagrangean relaxation)
3. Charles Colbourn, Combinatorics of Network Reliability, Oxford University Press, 1987 (Chapters 1 and 2)
4. George Nemhauser and Laurence Wolsey, Integer and Combinatorial Optimization, 1988 (Part I)

Project Team Participants:

Workshop Schedule

Back to Mathematical Modeling in Industry

Back to top of page