We present an overview of the exact methods for channel assignment in cellular networks together with a new linear 0-1 column generation formulation. After a general statement of the channel assignment problem as expressed nowadays in practice, we review in detail the exact methods of the literature and comment on their computational experiments. We next discuss two mathematical formulations for which we consider the objective of minimizing the interference level. The first one corresponds to a straightforward formulation of the problem and has already been considered (at least partially) by several authors. The second one is a new linear 0-1 column generation formulation where each variable corresponds to a potential cell assignment for a given channel (or channel block). We provide some promising preliminary results with the second formulation on some urban network data provided by Bell Mobilité.
Published April 1998 , 21 pages