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

Abstract 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.