Publication details

Saarland University Computer Science

Feasible Cellular Frequency Assignment Using Constraint Programming Abstractions

Joachim Paul Walser

Proceedings of the Workshop on Constraint Programming Applications, in conjunction with the Second International Conference on Principles and Practi, August 1996

The contribution of this paper is twofold. We present a new method for feasible cellular frequency assignment, a hard combinatorial optimization problem from telecommunications. Frequency assignment problems arise when a cellular radio network has to be established. Given a number of base stations, the goal is to assign each a number of frequencies, subject to given interference restrictions. We develop a transformation technique that allows for approximate optimization of multiple criteria: First, the original problem is transformed, thereby reducing the allowed number of distinct frequencies. In a second stage, the frequency span is compressed. Both stages exploit the cell-structure of the problem formulation. Preliminary experiments on randomized problems examine the effectiveness of the approach with respect to both criteria.
As we proceed in solving the subproblems that arise, we identify certain key programming abstractions (such as constraints, propagation and search). We argue that if these abstractions are supported by a programming language, they can greatly speed up the search for an efficient algorithm. We exemplify certain aspects of the modelling in Oz, a higher-order concurrent constraint language.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009