Frequency assignment in mobile radio systems using branch-and-cut techniques

We present a new exact method to plan frequency assignment for mobile radio systems in a geographical region. Frequencies are to be assigned to 'cells' so that the required service is performed under the particular constraint that the overall noise-signal ratio, related to interference, should not exceed a given level for each cell-frequency pair. This NP-hard problem is formulated as an Integer Linear Program and solved by an exact branch-and-cut technique, based on strong cutting planes. We start with very few constraints and use separation procedures to detect the violated constraints. The method and its implementation are tested on a library containing 85 real-world instances provided by CSELT, a major research laboratory operating with TIM (one of the Italian mobile radio system managers). We report the exact solution of instances with up to 203 cells within acceptable computing time. (C) 2000 Elsevier Science B.V. All rights reserved.