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 conglomeration linked together on a ring architecture, given the expected demands between the centers and an essentially unlimited availability...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1998-09, Vol.46 (5), p.719-728
Main Authors: Sutter, Alain S, Vanderbeck, Francois, Wolsey, Laurence
Format: Article
Language:English
Subjects:
(Tele)communications
Algorithms
Applied sciences
Architecture
assignment of equipment
comparison of safety policies
Exact sciences and technology
Flows in networks. Combinatorial problems
Heuristic
Heuristics
heuristics and decomposition algorithms
Integer programming
Integers
Mathematical rings
Multiplexers
Operational research and scientific management
Operational research. Management science
Operations research
Optimization
Simulated annealing
Studies
Systems, networks and services of telecommunications
Telecommunications
Telecommunications and information theory
Telecommunications industry
Transmission and modulation (techniques and equipments)
Transportation demand
Variable costs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 conglomeration 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 have been developed for the basic problem and several variants. France Telecom is particularly interested in validating the effectiveness of the heuristics. An exact algorithm based on integer column generation is shown to provide tight performance guarantees, and in most cases to give provable minimum cost solutions. Column generation is used even though the subproblems are strongly NP -hard and are solved by standard mixed integer programming software. In addition, the Master Problems involve both integer columns and integer variables, whereas these are 0–1 in most reported applications.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.46.5.719