Column generation for frequency assignment in slow frequency hopping networks
Lehrstuhl 2 für Mathematik, RWTH, , Aachen, Germany
EURASIP Journal on Wireless Communications and Networking 2012, 2012:253 doi:10.1186/1687-1499-2012-253Published: 14 August 2012
This article deals with the frequency assignment problem (FAP) in slow frequency hopping (GSM) networks, a generalization of the classical FAP. Due to symmetry in the solutions, a natural integer linear programming formulation does not yield a good solution procedure. Instead, we decompose the co-channel and adjacent channel interference minimization and develop a two-stage algorithm. The co-channel optimization problem is solved with a column generation model, whereas the second stage is solved by a cutting plane approach. Computational experiments reveal, that although no optimal solutions can be guaranteed, the approach provides promising results, both regarding practical applicability and further research potential.