Survivable network design with quality of service constraints : extended formulations and Benders decomposition
(2010)
Files
PhDQuentinBotton629-2010.pdf
Open Access - Adobe PDF
- 13.25 MB
Details
- Authors
- Supervisors
- Abstract
- (en) In this thesis we study the survivable network design problem applied to the telecommuni- cations industry. For obvious reasons, networks have to be survivable, in other words, they have to work even in case of failure (edge or node failure). In a first part of this thesis, the objective is to determine for each edge of the network the optimal capacity to install allowing connectivity for each commodity. To ensure surviv- ability, we assume that each edge of the given network, represented by a graph G = (V;E), can break down independently and we impose that at most one edge can be broken at the same time. For each edge ij in E we consider an independent failure scenario in which we have to ensure connectivity in a new graph where the given broken edge ij is removed from the edge set E. We propose a formulation for this problem and a cutting plane algorithm based on the Benders decomposition to improve the time needed to reach optimality. Then in a second part of this thesis, we consider the uncapacitated design problem in which the main objective is to determine the optimal topology (the minimum cost topology) of the network by choosing among all the potential edges, the ones on which to install capacity in order to send flows for a predetermined set of commodities. This time, to ensure survivability, we propose to find for each distinct commodity at least K edge-disjoint paths. This ensures that if (K-1) edges fail, the network keeps the possibility to send demands on the remaining path. Nowadays, due to the big expansion of telecommunications applications like audio, video, IP telephony,... survivability is no more the only key criteria for customers. New consid- erations linked to the quality of the service become more and more important. For these applications, the delay, which is closely related to the length of the paths used for routing, plays an important role. That is the reason why we propose to add new constraints bounding the length of the paths. Consequently we decide to analyze, in this thesis, the survivable network design problem with hop constraints. Based on an alternative representation of the graph (also called the layered graph) we give an extended formulation for this kind of problem and we formulate and prove some nice properties for the single commodity case. Given the nice structure of the problem and the huge number of variables and constraints, we study also the multicommodity case using the Benders decomposition, some branch-and-cut algorithms and an heuristic to reduce the CPU time. Finally we study a variation of the problem where we consider two groups of edges, the natural and the reliable edges. We show how this new problem becomes more complicated than the original one, we apply also the Benders decomposition and we conclude with an economical analysis of the impact of this new class of reliable edges.
- Affiliations
Citations
Botton, Q. (2010). Survivable network design with quality of service constraints : extended formulations and Benders decomposition. https://hdl.handle.net/2078.5/130995