Doubling or Splitting: Strategies for Modeling and Analyzing Survivable Network Design Problems
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 containi...
| Main Authors: | , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5142 |
| _version_ | 1826211646587011072 |
|---|---|
| author | Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash |
| author_facet | Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash |
| author_sort | Balakrishnan, Anantaram |
| collection | MIT |
| 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. |
| first_indexed | 2024-09-23T15:09:17Z |
| format | Working Paper |
| id | mit-1721.1/5142 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:09:17Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/51422019-04-12T08:06:47Z Doubling or Splitting: Strategies for Modeling and Analyzing Survivable Network Design Problems Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash 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. 2004-05-28T19:25:02Z 2004-05-28T19:25:02Z 1994-07 Working Paper http://hdl.handle.net/1721.1/5142 en_US Operations Research Center Working Paper;OR 297-94 2870083 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash Doubling or Splitting: Strategies for Modeling and Analyzing Survivable Network Design Problems |
| title | Doubling or Splitting: Strategies for Modeling and Analyzing Survivable Network Design Problems |
| title_full | Doubling or Splitting: Strategies for Modeling and Analyzing Survivable Network Design Problems |
| title_fullStr | Doubling or Splitting: Strategies for Modeling and Analyzing Survivable Network Design Problems |
| title_full_unstemmed | Doubling or Splitting: Strategies for Modeling and Analyzing Survivable Network Design Problems |
| title_short | Doubling or Splitting: Strategies for Modeling and Analyzing Survivable Network Design Problems |
| title_sort | doubling or splitting strategies for modeling and analyzing survivable network design problems |
| url | http://hdl.handle.net/1721.1/5142 |
| work_keys_str_mv | AT balakrishnananantaram doublingorsplittingstrategiesformodelingandanalyzingsurvivablenetworkdesignproblems AT magnantithomasl doublingorsplittingstrategiesformodelingandanalyzingsurvivablenetworkdesignproblems AT mirchandaniprakash doublingorsplittingstrategiesformodelingandanalyzingsurvivablenetworkdesignproblems |