Feasible Cellular Frequency Assignment Using Constraint Programming Abstractions. In Proceedings of the First Workshop on Constraint Programming Applications (in conjunction with the Second International Conference on Principles and Practice of Constraint Programming, CP-96), Cambridge, MA, 1996. Postscript , Postscript slides

Abstract:

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. The optimization objectives of our technique are first to minimize the number of distinct frequencies and second to compress the frequency span. We develop a two-stage approximation strategy that exploits the cell structure of the formulation. Preliminary experiments on randomized problems show the effectiveness of the approach.
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.