Optimization Online


On the hop-constrained survivable network design problem with reliable edges

Quentin Botton (quentin.botton***at***uclouvain.be)
Bernard Fortz (bernard.fortz***at***ulb.ac.be)
Luis Eduardo Neves Gouveia (legouveia***at***fc.ul.pt)

Abstract: In this paper, we study the hop-constrained survivable network design problem with reliable edges. Given a graph with non-negative edge weights and node pairs Q, the hop-constrained survivable network design problem consists of constructing a minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. In this paper, we propose and study the hop-constrained survivable network design problem with so-called reliable edges where in addition, we consider a subset of edges that are not subject to failure. We study two variants (a static problem where the reliability of edges is given, and an upgrading problem where edges can be upgraded to the reliable status at a given cost). We adapt for the two variants an extended formulation proposed in Botton et al (2011) for the case without reliable edges. As before, due to the huge number of variables and constraints included in the extended formulations, we use Benders decomposition to accelerate the solving process. We develop an exact branch-and-cut algorithm and a fix-and-branch heuristic. Our computational results indicate that these two variants appear to be more difficult to solve than the original problem (without reliable edges). We conclude with an economical analysis which evaluates the incentive of using reliable edges in the network

Keywords: Network design, Survivability, Hop constraints, Benders decomposition, Branch-and-cut

Category 1: Network Optimization

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 04/05/2012
Entry Accepted: 04/05/2012
Entry Last Modified: 04/25/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society