Comparison of column generation models for channel assignment in cellular networks

We study several formulations of the channel assignment problem in an FDMA network as a linear integer 0-1 program. We consider the objective of minim izing the unsatisfied channel demand while satisfying the co-channel, the a djacent channel and the antenna channel spacing constraints. We compare the formulations according to two criteria: the case with which their linear p rogramming relaxations can be solved, and the quality of the bounds provide d by these relaxations. We show that the best lower bound is provided by on e of the set covering formulations, while the other two formulations provid e the same lower bound. We present computational results that support the t heoretical comparison of the models. (C) 2001 Elsevier Science B.V. All rig hts reserved.