Groupe d’études et de recherche en analyse des décisions

G-98-39

A Column Generation Approach for the Exact Solution of Channel Assignment Problems

et

We propose a 0-1 column generation model for the problem of channel assignment in a cellular network, with the objective of minimizing the unsatisfied channel demand while providing a channel assignment with an acceptable interference level. The formulation takes into account both co-channel and adjacent channel constraints, as well as antenna spacing ones. The 0-1 linear program is solved with a branch-and-cut method where the solution of the continuous relaxation includes a shortest path problem with resource constraints. Preliminary results are presented on an urban network of Bell Mobilité. Performances are compared with those of the other exact approaches of the literature.

, 14 pages