Design of capacitated multicommodity networks with multiple facilities

This paper addresses the problem of designing a multicommodity network using several facilities with different costs and capacities. The problem is addressed in a special context of designing private telecommunications networks using Fractional-T1 services. The algorithm starts from any given solution of the problem and gradually improves it by solving a series of subproblems, arriving at a local minimum. The subproblem is defined over a subset of links, called the subnetwork, by using one of the links as the base link. It is shown that the subproblem can be formulated as a multiple choice knapsack problem that is solved by dynamic programming. Computational results and lower bounds are reported on problems of up to 20 nodes and up to 3 facilities. On most problems, the algorithm produces solutions within about 5% of lower bound on the average. Although it was not possible to compute lower bounds for larger problems, heuristic solutions and running times are reported for problems of up to 99 nodes and four facilities.