Least-cost network topology design for a new service

Autor:	Jennifer Ryan, Micheal Lee, Fred Glover
Rok vydání:	1991
Předmět:	Mathematical optimization Computer science Theory of computation General Decision Sciences Topology (electrical circuits) Decision rule Management Science and Operations Research Network topology Greedy algorithm Metaheuristic Tabu search Integer (computer science)
Zdroj:	Annals of Operations Research. 33:351-362
ISSN:	1572-9338 0254-5330
DOI:	10.1007/bf02073940
Popis:	We describe an implementation of the tabu search metaheuristic that effectively finds a low-cost topology for a communications network to provide a cenlialized new service. Our results are compared to those of a greedy algorithm which ^jplies corresponding decision rules, but widioul the guidance of the tabu search framework. These problems are difficult computationally, representing integer programs thai can involve as many as 10,000 integer variables and 2000 constraints in practical applications. The tabu search results approach succeeded in obtaining significant improvements over the greedy approach, yielding optimal solutions to problems small enough to allow independent verification of optimality status and, more generally, yielding both absolute and percentage cost improvements that did not deteriorate with increasing problem size.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::c7f6c0cdc5153f6065b531de1bfc231f https://doi.org/10.1007/bf02073940 Zobrazit plný text záznamu Plný text ve formátu PDF