Least-cost network topology design for a new service: An application of tabu search

The authors describe an implementation of the tabu search metaheuristic that effectively finds a low-cost topology for a communications network to provide a centralized new service. The present results are compared to those of a greedy algorithm which applies corresponding decision rules, but without the guidance of the tabu search framework. These problems are difficult computationally, representing integer programs that can involve as many as 10,000 integer variables and 2000 constraints in practical applications. The tabu search results approach succeeded in obtaining significant improvements over the greedy approach, yielding optimal solutions to problems small enough to allow independent verification of optimality status and, more generally, yielding both absolute and percentage cost improvements that did not deteriorate with increasing problem size.