A comparison of problem decomposition techniques for the FAP

作者：Colombo Gualtiero^*; Allen Stuart M

来源：Journal of Heuristics, 2010, 16(3): 259-288.

DOI：10.1007/s10732-009-9116-4

• Frequency assignment
• Problem decomposition
• Graph partitioning
• Simulated annealing

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.

• 出版日期2010-6