The frequency assignment problem (FAP) we study is described as follows. A set of transmission links needs to be established in order to enable communication between a set of points. With each link we associate a set of possible choices of frequencies. The assignment of a frequency to a link has to be done such that no interference occurs between any pair of links, i.e. such that for every pair of links the frequencies assigned to these links differ by a prespecified amount, possibly zero. The objective is to minimize the number of of frequencies that are used. We discuss different formulations of FAP, and how to generate good lower bounds that can be used in a branch-and-bound algorithm. We also briefly discuss how to find good feasible solutions, and give further references in this direction.

This is joint work with: C.P.M. Van Hoesel, A. Hipolito, and B. Jansen

A constraint satisfaction problem (CSP) consists of named variables which need to be assigned values, subject to some conditions. These conditions (constraints) limit the admissible assignments of values to certain subsets of the variables.

Many real world problems can be expressed as CSPs by choosing appropriate variables and modeling their interdependence using constraints. In particular we might choose to model a radio assignment problem by choosing as variables the frequencies and positions of a certain set of transceivers. Clearly there will be constraints involving both the position and the frequency of these transceivers. At least it must be the case that nearby transceivers must use widely separated frequencies.

In this talk we consider different aspects of this modeling procedure by exposing connections between CSPs and other mathematical structures. These different views of a CSP naturally lead to different insights.

Lastly we will look at the original representation of a problem as a CSP. We will see that the initial choice of variables and their associated constraints can have enormous computational significance.

Dynamic Channel Assignment (DCA) is being increasingly used for cellular/cordless telephone applications, because in principle it can support higher levels of fluctuating/bursty traffic without the need for detailed frequency planning.

Firstly, a typical propagation environment will be outlined. Such environments have non-uniform propagation characteristics as a result of shadowing effects, often caused by buildings and terrain. Secondly, a Distributed Dynamic Channel Assignment (DDCA) scheme will be explained, which uses local interference measurements at the transmitter site to determine the most suitable channel for transmission. Lastly, the DDCA scheme will be compared with "All-Knowing" DCA schemes which are intended to assign channels to users in a "Quasi-Optimum" configuration.

The first planning stage in the design of a large scale cellular networks usually involves positioning base stations in a certain regular pattern. Such a pattern can often be considered as a finite part of an infinite lattice in the plane. The conditions that, in the area covered by the network, the interference from co-channel and neighbouring channels is below a certain value can be translated into constraints on the use of channels. These constraints will involve the distance between transmitter pairs in the network.

In the talk, I shall discuss some of the methods developed in assigning channels to transmitters placed on an infinite lattice. Particular attention will be paid to methods that guarantee optimal or close to optimal assignments. The techniques used in the design and analysis of these methods vary from straightforward heuristic arguments to more advanced algebraic and geometrical tools.

The frequency assignment problem is an example of a combinatorial optimization problem: from a discrete set of possible assignments, select the `cheapest one'. Combinatorial problems are often modeled by a `Linear Programming' formulation (LP). Here, the objective, as well as the restricted combinations, are given in linear forms. Current state-of-the-art software enables us to solve large instances of these LP-models. However, often there is an additional requirement that the variables take only integral values. We discuss methods for solving these Integral Linear Programming problems using genuine LP-formulations as subproblems. Several schemes are discussed, such as Branch-and-Bound, Cutting-Planes, and Branch-and-Cut.

Tabu search is a computational procedure which has its roots going back to the late 1960s and early 1970s. It is now an established technique for solving difficult optimisation problems. This presentation will detail the fundamentals of the basic tabu search procedure, using examples to clarify its operation.

The idea behind tabu search is to derive and exploit a collection of principles for intelligent problem solving. A fundamental characteristic of the technique is the use of a flexible memory. This memory allows tabu search to create and exploit structures for taking advantage of various information obtained over the history of the search. The memory structures of tabu search operate by reference to four principal elements (recency, frequency, quality and influence).

Results will be presented showing the effectiveness of tabu search (and some hybrids) for both fixed span and minimum span frequency assignment.

Finally, a description using meta-heuristics (particularly genetic algorithms and simulated annealing) to find good initial orderings for sequential (greedy) frequency assignment algorithms will be given.

This talk will complement the presentation by George Smith, which will contain a general description of the simulated annealing and genetic algorithm paradigms and their application to frequency assignment.

Good and computationally feasible lower bounds on the number of frequencies needed to achieve a certain telecommunications function are essential for the efficient use and allocation of the radio-spectrum. On the one hand they provide the absolute minimum on the number of frequencies needed, and on the other they reveal the structural characteristics of the transmiters network that affect the number of frequencies to be allocated. Often, identification of these characteristics, or "obstacles", leads to efficient and at times optimal allocation methods.

In this talk we show how Polyhedral and Mathematical Programming Theory can be used to obtain such bounds.

We introduce the class of partial constraint satisfaction problems (PCSP), and give a {0,1}-programming formulation of PCSP. As examples of the class of problems studied we mention the frequency assignment problem and the maximum satisfiability problem. We define the partial constraint satisfaction polytope as the convex hull of feasible solution of PCSP. We present some classes of facet defining inequalities, and lifting theorems for this polytope. Computational results in the context of solving the crossover in a genetic algorithm for the frequency assignment problem show that these valid inequalities reduce the gap between LP-value and IP-value substantially. This is joint work with Arie Koster and Stan Van Hoesel.

In many modern radio systems, for example mobile telephony and communications networks, the demand for spectrum varies with time. There may be variations over both short time-scales, comparable to the duration of a single connection, and over longer scales, reflecting daily or weekly fluctuations in demand. The question arises of how to make best use of the available radio channels in such circumstances. The need to adapt assignments in real time dictates the type of algorithms that may be considered. This talk will examine the strategies that have been proposed in the past and, in the light of topics to be discussed in other talks, suggest areas where the future advances might lie.

The T-coloring problem introduced by Hale arose from the channel assignment problem. Fix a finite interference set T of nonnegative integers, with 0 in T. A T-coloring of a simple graph G=(V,E) is a function f: V->{0,1,2,...} such that for {u,v} in E(G), |f(u)-f(v)| is not in T. Let sigma_n denote the optimal span of the T-colorings f of the complete graph K_n, i.e., sigma_n = min_f {max_{u,v in V} |f(u)-f(v)|}. It was shown by Rabinowitz and Proulx that the asymptotic T-coloring efficiency R(T), defined as the limit as n tends to infinity of sigma_n/n, exists for every set T. Griggs and Liu proved a stronger result that the difference sequence {sigma_{n+1} - sigma_n} is eventually periodic for any T. Furthermore, the same authors proved that the greedy (first-fit) T-coloring of K_n also leads to an eventually periodic sequence. We survey these results in connection with earlier work of Cantor and Gordon on sequences with missing differences in T. Fix a set of integers D, the distance graph G(Z,D) has Z as the vertex set; and two vertices u and v are adjacent if |u-v| is in D. We prove R(T) is the lower bound of chi(Z,D), the chromatic number of G(Z,D), provided D=T-{0}. This result can be used to solve some problems in T-colorings or chromatic number of distance graphs.

Given a set V of points in the plane and given d>0, let G(V,d) denote the graph with vertex set V and with distinct vertices u and v adjacent whenever the Euclidean distance d(u,v) between them is less than d. The most simplified and basic version of the channel assignment problem involves colouring such `proximity' graphs. We need to assign radio channels (colours) to transmitters (points in V) to avoid interference. In order to avoid getting lost in details we consider the case when d is large. It turns out that we can make quite precise statements in the limit; and we find for example that if the set V has finite positive upper density, then the ratio of the chromatic number chi to the clique number omega tends to 2\sqrt{3}/pi (approx 1.103) as d tends to infinity.

However, for channel assignment problems we want to consider more general trade-offs between Euclidean distance and channel separation. Suppose that we are given a vector d = (d_0,d_1,...,d_{k-1}) where d_0 >= d_1 >= ... >= d_{k-1} >= 0. Call a colouring f:V -> { 1,2,..,t } d-legal if d(u,v) < d_i => |f(u) - f(v)| > i, and let chi(d;V) be the least t for which there is such a colouring. Suppose that d = d x where x is fixed and d tends to infinity. Are there results for this case corresponding to the above result for ordinary colourings (the case k=1)? We find that, if V has upper density sigma, then as d -> infinity, the ratio chi(d x;V) / d^2 tends to a limit sigma f(x). We give some partial results about the limit, focussing on the case k=2 with just two distances d_0, d_1. The upper bounds correspond to general approaches for finding assignments that may be useful in practice.

Use of the radio spectrum in the United Kingdom has shown dramatic growth over the last ten years, driven forward by Government policy to stimulate competition through liberalisation and privatisation in the telecommunications and broadcasting industries. This paper outlines the economic benefits flowing from exploitation of the spectrum and its importance to the UK economy. The paper outlines the need for new approaches to spectrum management - to gain the most effective utilisation of this vital natural resource. A 'balanced toolkit' of spectrum pricing; funding arrangements to promote spectrum efficiency; and continued regulation is described. UK proposals are placed in a context of other initiatives around the world.

This talk describes the application of the general heuristics, genetic algorithms and simulated annealing, to frequency assignment. We start by describing the basic algorithms and reporting the various representations and operators used by different authors.

Emphasis is placed on the practical issues involved in network planning and how this affects the assignment problem. We report results for a real wireless problem instance using a range of techniques and representations, showing how the adopted approaches can be extended to include frequency hopping in GSM networks.

This is joint work with T. Clark at Nortel Technology.

Frequency assignment problems can be treated as generalised colouring problems in graphs known as constraint graphs. A clique in a constraint graph is a (maximal) complete subgraph. The span of an assignment is the difference between the largest channel used and the smallest channel used. Cliques can be used for finding lower bounds for the span of an assignment. In general, clique bounds may not always be strong for colouring problems, as there exist graphs with no large cliques requiring an arbitrarily large number of colours. However, for the constraint graphs typical of frequency assignment problems, bounds found from cliques are often good.

One useful bound is based on the length of the shortest Hamiltonian path in the graph and has become known as the Travelling Salesman Bound. This is often tight for cellular problems, but may need improvement for other types of problem. It is important that this bound is applied to a suitable clique or "near clique" and not to the whole constraint graph, or the bound may be very weak.

Once the clique or "near clique" that give the best bound has been identified, a frequency assignment algorithm may be more effective if it is applied to this subgraph first. The assignment of the subgraph can then be fixed and the assignment can be extended to the full constraint graph.

Radio astronomy is a passive service: a receiver-only radiocommunication application. It is not able to influence the transmitting source. All other services use both a transmitter and a receiver, which man can manipulate. They are called "active" services. Radio astronomical signals are about 9 orders of magnitude weaker than those used by active services. This difference is a major cause of the vulnerability of radio astronomy to man-made interference.

This interference introduces a "radio-climate" in telecommunication land with parameters depending on frequency, spatial coordinates and time. Furthermore, this interference can be either intended or unintended, legal or illegal, which imply that the nature of the problem is dynamic. To answer this, a dynamic solution is required, which needs cooperation with administrations, active spectrum users and colleagues on the one hand and adequate system design on the other hand. The different nature of passive and active spectrum use implies a multidimensional regulatory approach.

This talk explains basic concepts of spectrum management. How the spectrum is managed has profound impact on the society, its prosperity, culture, and security. Spectrum management embraces all activities involved in rational use of spectrum resources used for radiocommunications and for other applications vital for society. These resources consist of radio frequencies and the geostationary satellite orbit, and are multi-dimensional.

The talk discusses the key problem that is the apparent scarcity of spectrum resources. That scarcity generates conflicts and hampers further development of all applications and activities dependent on radio. The spectrum scarcity is in part due to deficiencies in spectrum management practices. Some of them are reviewed together with possible solution ways and means. Among others, a need for wider application of advanced mathematical methods and computer tools is stressed.

The radio frequency channel assigned to a transmitter is only one of the basic variables in radio spectrum management. Another one is the power. This talk describes how to optimally assign power to a collection of radio transmitters under constraints. The constraints concern the physical realizability and electromagnetic compatibility among the transmitters and with the environment. The frequency channels are assumed to be already assigned to each transmitter.

The aim of optimization is to minimize the amount of the frequency spectrum and geographical space occupied by all the transmitters together. "Occupied" means denied to other uses. Normally, the area occupied by a transmitter increases with the power radiated. Consequently, the minimum total power means the minimal space occupied, or maximal number of transmitters operating over a given area. In view of introduction of spectrum markets where the operator pays for the spectrum and space occupied, the issue takes also an economic dimension. The minimum of the power radiated means also minimal power consumption, an important aspect in many applications that also has a cost impact.

The talk discusses the constraints, proposes a new compatibility criterion and treats the optimization task as a Linear Programming problem.