A mathematical programming approach to the channel assignment problem in radio networks

The demand for mobile telephone service is increasing rapidly. A new formulation for the channel assignment problem (CAP) is proposed. The CAP has been formulated as an integer linear programming problem including compatibility and requirement constraints. For the solution of the resulting formulation conventional branch and bound methods have been used. The exploitation of the problem´s special structure can improve the computational efficiency of the algorithm used. The algorithm has been applied to different benchmark problems that have appeared in the literature. The presented examples illustrate that using the proposed formulation and a specially designed branch and bound algorithm is possible to solve optimally and efficiently fairly large channel assignment problems