| dc.description |
Survivability is becoming an increasingly important criterion in network design. This paper studies formulations, heuristic worst-case performance, and linear programming relaxations for two classes of survivable network design problems: the low connectivity Steiner (LCS) problem for graphs containing nodes with connectivity requirement of 0, 1, or 2, and a more general multi-connected network with branches (MNB) that requires connectivities of two or more for certain (critical) nodes and single connectivity for other secondary nodes. We consider both unitary and nonunitary MNB problems that respectively require a connected design or permit multiple components. Using a doubling argument, we first show how to generalize heuristic bounds of the Steiner tree and traveling salesman problems to LCS problems. We then develop a disaggregate formulation for the MNB problem that uses fractional edge selection variables to split the total connectivity requirement across each critical cutset into two separate requirements. This model, which is tighter than the usual cutset formulation, has three special cases: a "secondary-peeling" version that peels off the lowest connectivity level, a "connectivity-dividing" version that divides the connectivity requirements for all the critical cutsets, and a "secondarycompletion" version that attempts to separate the design decisions for the multi-connected network from those for the branches. We examine the tightness of the linear programming relaxations for these extended formulations, and then use them to analyze heuristics for the LCS and MNB problems. Our analysis strengthens some previously known heuristic-to-IP worst-case performance ratios for LCS and MNB problems by showing that the same bounds apply to the heuristic-to-LP ratios using our stronger formulations. |
|