A simulated annealing approach to communication network design

Marcus Randall*, Graham McMahon, Stephen Sugden

*Corresponding author for this work

Research output: Contribution to journalArticleResearchpeer-review

35 Citations (Scopus)
171 Downloads (Pure)


This paper explores the use of the meta-heuristic search algorithm Simulated Annealing for solving a minimum cost network synthesis problem. This problem is a common one in the design of telecommunication networks. The formulation we use models a number of practical problems with hop-limit, degree and capacity constraints. Emphasis is placed on a new approach that uses a knapsack polytope to select amongst a number of pre-computed traffic routes in order to synthesise the network. The advantage of this approach is that a subset of the best routes can be used instead of the whole set, thereby making the process of designing large networks practicable. Using simulated annealing, we solve moderately large networks (up to 30 nodes) efficiently.

Original languageEnglish
Pages (from-to)55-65
Number of pages11
JournalJournal of Combinatorial Optimization
Issue number1
Publication statusPublished - 1 Mar 2002


Dive into the research topics of 'A simulated annealing approach to communication network design'. Together they form a unique fingerprint.

Cite this