Frequency allocation and linear programming


M. Hellebrandt, F. Lambrecht, R. Mathar, T. Niessen, R. Starke,


        The present paper deals with optimal fixed channel assignment for large real-world cellular radio networks. Examples are taken from data of the D2-network, operated by Mannesmann Mobilfunk (MMO) in Germany. Because of the huge size of the problems an exact optimal solution is presently out of reach. We present a heuristic iterative approach which performs extremely well, and significantly outperforms channel designs presently used by network operators. The basic ingredients of our approach are 1. fast and well established simple heuristics as initial assignments, 2. splitting the whole problem into smaller subproblems which can be optimized efficiently by solving a binary linear program (BLP), and repeating this process iteratively, 3. past-processing the resulting near-optimal design to avoid undesirable properties. A lot of detailed problems must be solved, such as a powerful preprocessing of constraints for the BLPs, and a carefull selection of the subproblems in 2. In summary, a very flexible tool is derived, also capable of taking into account external constraints from practical requirements.

BibTEX Reference Entry 

	author = {Martin Hellebrandt and Frank Lambrecht and Rudolf Mathar and Thomas Niessen and Reiner Starke},
	title = "Frequency allocation and linear programming",
	pages = "617-621",
	booktitle = "{IEEE} VTC",
	address = {Houston},
	year = 1999,


 Download paper  Download bibtex-file

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights there in are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.