DESIGN OF CAPACITATED NETWORKS WITH TREE CONFIGURATIONS

This paper considers the problem of designing a capacitated network wi th a tree configuration (CTP). For a given set of nodes with their cap acities, k types of link facilities with various characteristics, acid installation cost for connecting each pair of nodes using each type o f link facility, the problem is to find a tree network which satisfies the given traffic requirements between all pairs of nodes and minimiz es total installation cost. We formulate (CTP) as an integer programmi ng problem using path variables. To solve the linear programming relax ation 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-a nd-cut algorithm with column generation where an efficient branching r ule is adopted. Computational results show that the algorithm can solv e practically-sized problems to optimality within a reasonable time.