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

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2000-06, Vol.123 (2), p.241-255
Main Authors: Fischetti, Matteo, Lepschy, Chiara, Minerva, Giuseppe, Romanin-Jacur, Giorgio, Toto, Ema
Format: Article
Language:English
Subjects:
Algorithms
Branch-and-cut
Frequency assignment
Integer linear programming
Integer programming
Linear programming
Operations research
Studies
Telecommunication systems
Telecommunications systems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(99)00254-4