1996
Joachim P. Walser
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