Premium
Exact solution of the centralized network design problem on directed graphs
Author(s) -
Gzara Fatma,
Goffin JeanLouis
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20061
Subject(s) - column generation , cutting plane method , lagrangian relaxation , spanning tree , steiner tree problem , mathematical optimization , branch and bound , directed graph , linear programming relaxation , interior point method , branch and cut , mathematics , relaxation (psychology) , constraint (computer aided design) , upper and lower bounds , tree (set theory) , point (geometry) , computer science , linear programming , integer programming , combinatorics , psychology , social psychology , mathematical analysis , geometry
We present a novel exact solution method for the centralized network design problem on directed graphs. The problem is modeled as the well‐known graph theoretic problem: the capacitated directed spanning tree problem. We propose a Lagrangian relaxation where the subproblem is a directed spanning tree with a degree constraint on the root. The master problem has an exponential number of constraints and variables. To solve it, we present a cut‐and‐column generation algorithm based on analytic centers. The latter solves a restricted master problem using a primal analytic center cutting plane method and strengthens the bound by generating columns that correspond to violated primal constraints. The Lagrangian bound is embedded within branch‐and‐bound leading to an interior point branch‐and‐price algorithm with cut generation. We use a dual interior point method to warm start the solution of the restricted master problem both after adding columns and after branching. We present numerical results indicating that the proposed approach outperforms the literature on the directed case. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(4), 181–192 2005