Erratum to Comparison of column generation models for channel assignment in cellular networks ?: [Discrete Appl. Math. 112 (2001) 217240]
We study several formulations of the channel assignment problem in an FDMA network as a linear integer 01 program. We consider the objective of minimizing the unsatisfied channel demand while satisfying the co-channel, the adjacent channel and the antenna channel spacing constraints. We compare the formulations according to two criteria: the ease with which their linear programming relaxations can be solved, and the quality of the bounds provided by these relaxations. We show that the best lower bound is provided by one of the set covering formulations, while the other two formulations provide the same lower bound. We present computational results that support the theoretical comparison of the models.
column generation channel assignment cellular network 01 integer linear program weighted independent set shortest path resource constraints branch-and-bound