Optimal Placement of ADD/DROP Multiplexers : Heuristic and Exact Algorithms

We study a problem that has arisen recently in the design of telecommunications transmission networks at France Telecom. Given a set of centers in a city or conglommeration linked together on a ring architecture, given the expected demands between the centers and an essentially unlimited availability of rings of fixed capacity on the network, assign demand pairs and corresponding add/ drop multiplexers to the rings so as to satisfy the demands and minimize the number of "costly" multiplexers installed. Heuristics based on simulated annealing and IP column generation algorithms have been developed for the basic probleul and several variants. The column generation algorithms provide tight. lower bounds that permit us to validate the effectiveness of the heuristics, and in many instances to derive guaranteed minimum cost solutions.