McGill Computer Networks Research Lab

The network design problem with reliability constraints is a problem where, given a finite set of nodes, the objective is a cost efficient selection of links and link capacities sufficient to satisfy the node-to-node traffic demands in normal and failed conditions. In this paper, we present a general mathematical model for this problem and a revised formulation which seems particularly appropriate for fiber optics networks. We also describe upper and lower hounding procedures
based on continuous relaxations of this modified formulation. Preliminary computational results are reported; they seem to indicate that the proposed bounds might prove suitable for a branch-and-bound approach of the problem.