A branch-and-cut algorithm for the frequency assignment problem

The frequency assignment problem (FAP) is the problem of assigning frequencies to transmission links such that no interference between signals occurs. This implies distance constraints between assigned frequencies of links. The objective is to minimize the number of used frequencies. We present an integer linear programming formulation that is closely related to the vertex packing problem. Although the size of this formulation is an order of magnitude larger than the underlying network of links, we use the integer linear programming formulation within a branch-and-cut algorithm. This algorithm employs problem specific and generic techniques such as reduction methods, primal heuristics, and branching rules to obtain optimal solutions. We report on computational experience with real-life instances. 1