A Cutting Plane Algorithm for Multicommodity Survivable Network Design Problems
INFORMS Journal on Computing · 1998 · Volume 10 · Issue 1
Abstract
We present a cutting plane algorithm for solving the following telecommunications network design problem: given point-to-point traffic demands in a network, specified survivability requirements and a discrete cost/capacity function for each link, find minimum cost capacity expansions satisfying the given demands. This algorithm is based on the polyhedral study described in [19]. In this article we describe the underlying problem, the model and the main ingredients in our algorithm. This includes: initial formulation, feasibility test, separation for strong cutting planes, and primal heuristics. Computational results for a set of real-world problems are reported.
Keywords
Capacitated networks, algorithms, cutting plane
Enable JavaScript for citation tools and additional paper interactions.