  


On the hopconstrained survivable network design problem with reliable edges
Quentin Botton (quentin.bottonuclouvain.be) Abstract: In this paper, we study the hopconstrained survivable network design problem with reliable edges. Given a graph with nonnegative edge weights and node pairs Q, the hopconstrained survivable network design problem consists of constructing a minimum weight set of edges so that the induced subgraph contains at least K edgedisjoint paths containing at most L edges between each pair in Q. In this paper, we propose and study the hopconstrained survivable network design problem with socalled 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 branchandcut algorithm and a fixandbranch 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, Branchandcut Category 1: Network Optimization Category 2: Combinatorial Optimization (Branch and Cut Algorithms ) Category 3: Integer Programming (Cutting Plane Approaches ) Citation: Download: [PDF] Entry Submitted: 04/05/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  