Benders decomposition for the hop-constrainted survivable network design problem

Q. Botton(quentin.bottonuclouvain.be)
B. Fortz(bfortzulb.ac.be)
L. Gouveia(legouveiafc.ul.pt)
M. Poss(mpossulb.ac.be)

Abstract: Given a graph with nonnegative edge weights and a set of pairs of nodes Q, we study the problem 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. Using the layered representation introduced by Gouveia, we present the first formulation for the problem valid for any K, L ≥ 1. We use a Benders decomposition method to efficiently handle the big number of variables and constraints. While some recent works on Benders decomposition study the impact of the normalization constraint in the dual subproblem, we focus here on when to generate the Benders cuts. We present a thorough computational study of various cutting plane and branch-and-cut algorithms on a large set of instances including the real based instances from SNDlib. Our best branch-and-cut algorithm combined with an efficient heuristic is able to solve the instances significantly faster than CPLEX 11. Then, we show that our Benders cuts contain the constraints used by Huygens et al. to formulate the problem for L = 2, 3, 4, as well as new inequalities when L ≥ 5.

Keywords: survivable network; edge-disjoint paths; hop-constrained paths; Benders decomposition; branch-and-cut algorithm

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Applications -- OR and Management Sciences (Telecommunications )

Citation: ULB, march 2010

Download: [PDF]

Entry Submitted: 03/09/2010
Entry Accepted: 03/09/2010
Entry Last Modified: 03/09/2010

Modify/Update this entry