Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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: Advanced Research Computing @ Cardiff (ARCCA)
Computer Science & Informatics
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 Edit Item