Benders Decomposition for the Hop-Constrained Survivable Network Design Problem
Quentin Botton, Bernard Fortz, Luis Gouveia, Michael Poss
INFORMS Journal on Computing · 2013 · Volume 25 · Issue 1
Abstract
Given a graph with nonnegative edge weights and node pairs 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 [Gouveia, L. 1998. Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. INFORMS J. Comput. 10 (2) 180–188], we present a formulation for the problem valid for any K , L ≥ 1. We use a Benders decomposition method to efficiently handle the large number of variables and constraints. We show that our Benders cuts contain constraints used in previous studies to formulate the problem for L = 2, 3, 4, as well as new inequalities when L ≥ 5. Whereas 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 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 12 on the extended formulation.
Keywords
survivable network, edge-disjoint paths, hop-constrained paths, Benders decomposition, branch-and-cut algorithm
Enable JavaScript for citation tools and additional paper interactions.