An Exact Algorithm for the Min-Interference Frequency Assignment Problem
Vittorio Maniezzo, Roberto Montemanni · 1999
In this paper we consider the Frequency Assignment Problem, where the objective is to minimize the cost due to interference arising in a solution. We use a quadratic 0-1 integer programming formulation of the problem as a basis to derive new lower bounds and problem reduction rules. A tree search algorithm, that uses the lower bounds and dominance criteria is also presented. Computational results are shown on standard benchmark instances from the literature. Keywords: Integer programming, branch-and-bound, telecommunications. 1. Introduction In recent years we have witnessed a tremendous growth of mobile communication networks. Several combinatorial optimization problems arise in the context of the design and management of such networks; their actual interest has fostered research on mathematical properties and solution techniques. The problem we consider in this paper is the Frequency Assignment Problem (FAP), a network management problem; we face also a special case of FAP named Rad...