Joachim P. Walser


BibTeX Entry

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.

Proceedings of the Workshop on Constraint Programming Applications, in conjunction with the Second International Conference on Principles and Practice of Constraint Programming (CP96), Aug 1996