Design of capacitated networks with tree configurations

This paper considers the problem of designing a capacitated network with a tree configuration (CTP). For a given set of nodes with their capacities, k types of link facilities with various characteristics, acid installation cost for connecting each pair of nodes using each type of link facility, the problem is to find a tree network which satisfies the given traffic requirements between all pairs of nodes and minimizes total installation cost. We formulate (CTP) as an integer programming problem using path variables. To solve the linear programming relaxation which has exponentially many variables, we develop a polynomial-time column generation procedure. Moreover, to tighten the formulation, an efficient preprocessing procedure is devised and some classes of valid inequalities are found. Using the results, we develop a branch-and-cut algorithm with column generation where an efficient branching rule is adopted. Computational results show that the algorithm can solve practically-sized problems to optimality within a reasonable time.