Arc and path-based formulations for survivable network design

Due to the recent increase in demand for data transfer, the design of robust and reliable networks is an important issue. A common routing problem encountered in such networks seeks to simultaneously route point-to-point demands across the network subject to capacity restrictions on its links. A feasible solution to this problem is called a multicommodity flow. Network designers must take care to build enough capacity and diverse routing paths through a network to ensure that feasible multicommodity flows exist in the network, even when components of the network fail. In this paper different methodologies are presented and compared to design a minimum cost survivable network that continues to support a multicommodity flow under any of a given set of failure scenarios. A failure scenario can consist of the simultaneous failure of more than one arc, with the option of failing a node by failing all the adjacent arcs to that node. As opposed to much of the previous work done in this field, we consider general failure scenarios. Two different modeling approaches are used to solve this problem: arc-based and path-based. Arc-based formulations contain variables that represent the amount of flow for each commodity on each arc, whereas path-based formulations use variables that represent the amount of total flow on an origin-destination path. We begin by providing mixed-integer programming formulations for each of these approaches, and demonstrate that these formulations require an immense amount of memory and computational time to solve even modest-size problem. Hence, different decomposition strategies are used to deal with the memory requirements. For our arc-based formulation, we employ a standard Benders' Decomposition approach. This technique requires the formulation of an integer first-stage master problem and several continuous second-stage subproblems. To reduce the computational time, the master problem is augmented by two different methods. Both of these augmentations are tested and compared. The best of these augmentations is further enhanced by preprocessing and cover constraints. For our path-based formulation, we develop a novel branch, price, and cut algorithm. This algorithm uses Benders' Decomposition as well as column generation to keep the problem size to the minimum. We computationally evaluate different variations of the arc-based and path-based approach, and provide recommendations for their use in practical applications.