Lower Bounds for Fixed Spectrum Frequency Assignment |
| |
Authors: | R Montemanni DH Smith SM Allen |
| |
Institution: | (1) Div. of Mathematics, University of Glamorgan, Pontypridd, CF37 1DL Wales, UK;(2) Dept. of Computer Science, University of Wales, Cardiff, P.O. Box 916, Cardiff, CF24 3XF Wales, UK |
| |
Abstract: | Determining lower bounds for the sum of weighted constraint violations in fixed spectrum frequency assignment problems is important in order to evaluate the performance of heuristic algorithms. It is well known that, when adopting a binary constraints model, clique and near-clique subproblems have a dominant role in the theory of lower bounds for minimum span problems. In this paper we highlight their importance for fixed spectrum problems. We present a method based on the linear relaxation of an integer programming formulation of the problem, reinforced with constraints derived from clique-like subproblems. The results obtained are encouraging both in terms of quality and in terms of computation time. |
| |
Keywords: | radio frequency assignment lower bounds fixed spectrum problems |
本文献已被 SpringerLink 等数据库收录! |
|