Connectivity-splitting models for survivable network design
The survivable network design (SND) problem seeks a minimum-cost robust network configuration that provides a specified number of alternate (edge-disjoint) paths between nodes of the network. For this problem, we present a family of new mixed-integer programming formulations whose associated linear programming relaxations can be tighter than that of the usual cutset formulation. The new formulations, called connectivity-splitting models, strengthen the cutset formulation by splitting the connectivity requirements across critical cutsets (with crossing requirements of at least two) into two separate requirements and strengthening the connectivity constraints across regular cutsets (with crossing requirements of one). As special cases of this broad modeling approach, we obtain three intuitive versions of the model. A connectivity-peeling version peels off the lowest connectivity level, a connectivity-dividing version divides the connectivity requirements for all critical cutsets, and an access-completion version separates the design decisions for critical cutsets from those for regular cutsets. These stronger formulations motivate several SND combinatorial heuristics and facilitate the analysis of their worst-case performance. Our bounds on the heuristic costs relative to the optimal values of the integer program and the linear programming relaxation of our tighter formulation are stronger than some previously known performance bounds for combinatorial heuristics. (C) 2003 Wiley Periodicals, Inc.
survivability network design integer programming heuristics worst-case performance model formulation