Optimal Placement of Add/Drop Multiplexers: Heuristic and Exact Algorithms

Alain S. Sutter, François Vanderbeck and Laurence Wolsey
Additional contact information
Alain S. Sutter: CNET, France Telecom, France
François Vanderbeck: Cambridge University, England
Laurence Wolsey: Université Catholique de Louvain, Louvain-la-Neuve, Belgium

Operations Research, 1998, vol. 46, issue 5, 719-728

Abstract: 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.

Keywords: (Tele)communications; assignment of equipment; comparison of safety policies; Integer programming; heuristics and decomposition algorithms (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.5.719 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:5:p:719-728

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().