Connectivity-splitting models for survivable network design

The survivable network design (SND) problem seeks a minimum cost set of edges that meet prescribed node connnectivity requirements. We present a new family of strong mixed integer programming formulations for this problem, examine the tightness of the associated linear programming relaxations, and then use the relaxations to analyze heuristics for several variants of the SND problem and its special cases. The new models are tighter than the usual cutset formulation when the network contains both regular nodes that must be connected to other nodes in the network and critical nodes with higher connectivity requirements. Our analysis provides stronger worst-case bounds or shows that some previously known worst-case performance ratios of heuristic to optimal (mixed integer programming) costs also hold relative to the optimal ratio of the heuristic to optimal linear programming values of these stronger formulations. The new formulations use fractional edge selection variables to split the connectivity requirements of the critical nodes into two separate requirements. We consider three versions of the model. A connectivity-peeling version peels off the lowest connectivity level, a connectivity-dividing version divides the connectivity requirements for all cutsets separating critical nodes, and a branch-addition version attempts to separate the design decisions for a multi-connected component of the network from those for the branches