Article ID: | iaor20023269 |
Country: | Netherlands |
Volume: | 107 |
Issue: | 1 |
Start Page Number: | 237 |
End Page Number: | 250 |
Publication Date: | Oct 2001 |
Journal: | Annals of Operations Research |
Authors: | Smith D.H., Montemanni R., Allen S.M. |
Keywords: | programming: integer |
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.