A comparison of problem decomposition techniques for the FAP

Colombo, Gualtiero B. and Allen, Stuart Michael ORCID: https://orcid.org/0000-0003-1776-7489 2010. A comparison of problem decomposition techniques for the FAP. Journal of Heuristics 16 (3) , pp. 259-288. 10.1007/s10732-009-9116-4

Full text not available from this repository.

Abstract

This paper proposes a problem decomposition approach to solve hard Frequency Assignment Problem instances with standard meta-heuristics. The proposed technique aims to divide the initial problem into a number of easier subproblems, solve them and then recompose the partial solutions into one of the original problem. We consider the COST-259 MI-FAP instances and other Cardiff University test problems in order to simulate larger and more realistic networks. For both benchmarks the standard implementations of meta-heuristics do not generally produce a satisfactory performance within reasonable times of execution. However, the decomposed assignment approach can improve their results, both in terms of solution quality and runtime.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Professional Services > Advanced Research Computing @ Cardiff (ARCCA) Schools > Computer Science & Informatics Research Institutes & Centres > Systems Immunity Research Institute (SIURI)
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Uncontrolled Keywords:	Frequency assignment - Problem decomposition - Graph partitioning - Simulated annealing
Publisher:	Springer
ISSN:	1381-1231
Last Modified:	18 Oct 2022 13:28
URI:	https://orca.cardiff.ac.uk/id/eprint/14008

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item