Groupe d’études et de recherche en analyse des décisions

G-2003-23

Exact Solution of the Centralized Network Design Problem on Directed Graphs

et

We present a novel exact solution method for the centralized network design problem on directed graphs. The problem is modelled as the well-known graph theoretic problem: the capacitated spanning directed tree problem. We propose a Lagrangian relaxation where the subproblem is a directed spanning tree with 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 that outperform the state-of-the-art for the directed and undirected cases.

, 23 pages