A simulated annealing approach to communication network design

Marcus Randall, Graham McMahon, Stephen Sugden

Research output: Contribution to journalArticleResearchpeer-review

29 Citations (Scopus)
17 Downloads (Pure)

Abstract

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
Volume6
Issue number1
DOIs
Publication statusPublished - 1 Mar 2002

Fingerprint

Network Design
Simulated annealing
Simulated Annealing
Communication Networks
Telecommunication networks
Telecommunication Network
Capacity Constraints
Knapsack
Heuristic Search
Polytope
Metaheuristics
Heuristic algorithm
Search Algorithm
Costs
Traffic
Synthesis
Subset
Formulation
Vertex of a graph
Model

Cite this

Randall, Marcus ; McMahon, Graham ; Sugden, Stephen. / A simulated annealing approach to communication network design. In: Journal of Combinatorial Optimization. 2002 ; Vol. 6, No. 1. pp. 55-65.
@article{d6939785b6d04b2cb74d7453357320a1,
title = "A simulated annealing approach to communication network design",
abstract = "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.",
author = "Marcus Randall and Graham McMahon and Stephen Sugden",
year = "2002",
month = "3",
day = "1",
doi = "10.1023/A:1013337324030",
language = "English",
volume = "6",
pages = "55--65",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer",
number = "1",

}

A simulated annealing approach to communication network design. / Randall, Marcus; McMahon, Graham; Sugden, Stephen.

In: Journal of Combinatorial Optimization, Vol. 6, No. 1, 01.03.2002, p. 55-65.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A simulated annealing approach to communication network design

AU - Randall, Marcus

AU - McMahon, Graham

AU - Sugden, Stephen

PY - 2002/3/1

Y1 - 2002/3/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0036498081&partnerID=8YFLogxK

U2 - 10.1023/A:1013337324030

DO - 10.1023/A:1013337324030

M3 - Article

VL - 6

SP - 55

EP - 65

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 1

ER -