Frequency Assignment

Frequency assignment is an important problem in the radiocommunication industry. In such a problem there is a radio communications network in a given region consisting of a set of transmitters. Each transmitter has a position in the region, a frequency spectrum, a certain power, and a directional distribution. The aim is to assign values to some or all of the properties of the transmitters so that certain criteria are satisfied. There are various types of frequency assignment problems. In this study we consider a version of the radio link frequency assignment problem (RLFA). In such a problem we are given a set of links $\{L_1,\ldots,L_n\}$, each consisting of a transmitter and a receiver. Each link must be assigned a frequency from a given set $F$. At the same time the total interference at the receivers must be reduced below an acceptable level using as few frequencies as possible. These problems are typically optimization problems but for the purposes of this study we treat them as satisfaction problems.

A RLFA problem can be modelled as a CSP where each transmitter corresponds to a variable. The domain of each variable consists of the frequencies that can be assigned to the corresponding transmitter. The interferences between transmitters are modelled as binary constraints of the form $\vert x_i-x_j\vert>s$, where $x_i$ and $x_j$ are variables and $s \geq 0$ is a required frequency separation. Such a constraint restricts the frequencies that the two transmitters can simultaneously be assigned, and in that way the interference between them is minimized. This is under the realistic assumption that the closer two frequencies are the greater is the interference between them. This binary model has been used extensively to represent RLFA problems, and numerous solution methods (CSP-based or other) have been proposed. Also, RLFA has been widely used as a benchmark to test new algorithms for binary constraints (mainly AC algorithms).

It has been argued that the standard binary model of frequency assignment problems fails to capture some important aspects of real problems, such as multiple interferences, resulting in non-optimal frequency assignments [Jeavons, Dunkin, BaterJeavons et al.1998,Watkins, Hurley, SmithWatkins et al.1998,BaterBater2000,Hodge, Hurley, SmithHodge et al.2002]. As a consequence, there have been some efforts to introduce more expressive methods that utilize non-binary constraints in frequency assignment (e.g. bater00,hodge02). There are many types of non-binary constraints that can be considered. The following ones have received attention:

co-channel constraints

- e.g., the frequencies assigned to $n$ transmitters are not all equal.

adjacent-channel constraints

- e.g., the frequencies assigned to $n$ transmitters are at least one frequency apart.

separation constraints

- e.g., the frequencies assigned to $n$ transmitters are at least $s$ frequencies apart.

Obviously, separation constraints generalize the adjacent-channel constraints. The first two types of constraints are typically very loose while the third can be tight. Separation constraints are used in densely constrained areas (representing conurbations in a region) where there is large number of links closely situated. In such cases, large separations in the frequencies of the transmitters must be imposed, resulting in tight constraints. We also consider a richer type of separation constraints: The frequencies assigned to a set of $n$ transmitters are at least $s$ frequencies apart and $n'$ transmitters among them are at least $s'$($>s$) frequencies apart from all the others. Note that some of the non-binary constraints can be equivalently decomposed into a clique of binary constraints (without introducing dual variables) resulting however in weaker propagation. An example is adjacent-channel constraints. Others cannot be equivalently expressed as a set of binary constraints unless a binary encoding is used. For example, co-channel constraints. As noted by Hodge et al. hodge02, only non-binary constraints of low arity can be utilized in practice. It has been shown that in many cases such constraints are sufficient to achieve very low interferences. Constraints of higher arity may offer improvements in the quality of solutions, but they tend to slow down the solution process to an extend that solving large real problems becomes infeasible.

In the empirical study presented here we are interested in comparing models of RLFA-type problems with non-binary constraints to the corresponding binary encodings and not in devising new efficient methods for solving RLFA problems. Since the available RLFA benchmarks follow the standard binary approach, to test the algorithms we generated non-binary problems by placing variables, corresponding to links, on a grid following the typical RLFA structure. That is, the problems consist of several groups of closely situated variables plus a few constraints that connect these groups. For example, such structures are depicted in Figure 11. This corresponds to the constraint graph of a binary RLFA problem which typically consists of a set of cliques (or near-cliques) of binary constraints and a small number of constraints connecting the various cliques (e.g. the benchmarks of cabon99). From the binary encodings we only considered the double since dual variables can have very large domains, which makes the DE inefficient.

Indicative results of the experiments we run are depicted in Table 6. In these experiments we posted only low-arity (i.e. 3-ary to 5-ary) separation constraints, as shown in Figure 11, and compared the performance of algorithm MGAC-2001 on the non-binary model of the problems to the performance of MAC-PW-ACd on the double encoding of the problems. We tried two implementations of MGAC-2001; one that utilizes specialized propagators for the separation constraints (written as functions), and another that operates on the extensional representation of the constraints. The first implementation was generally faster, so all the results of MGAC-2001 presented below refer to the intentional implementation. The double encoding was built by translating the separation constraints into lists of allowed tuples in a preprocessing step.

Figure 11: Examples of RLFA problems with non-binary separation constraints.

Table 6: Comparison of algorithms on RLFA problems with separation constraints. $arity$ is the maximum constraint arity. Run times are given in seconds. A dash (--) is placed wherever the algorithm did not finish its run within 12 hours of cpu time.

	problem			$n$			$e$			$arity$			MGAC-2001			MAC-PW-ACd
													nodes - time			nodes - time
	$prob1$ (easiest)			48			25			4			583 - 1.51			48 - 0.36
	$prob1$ (median)			48			25			4			18161268 - 39518.71			50 - 0.34
	$prob1$ (hardest)			48			25			4			--			--
	$prob2$ (easiest)			44			21			4			56474 - 26.46			172071 - 219.06
	$prob2$ (median)			44			21			4			304676 - 169.01			305588 - 504.06
	$prob2$ (hardest)			44			21			4			53654514 - 4220.21			68771412 - 24133.45
	$prob3$ (easiest)			54			24			5			103 - 13.45			0 - 6.42
	$prob3$ (median)			54			24			5			2134 - 14.14			2569 - 53.18
	$prob3$ (hardest)			54			24			5			4194 - 115.12			0 - 5.64
	$prob4$ (easiest)			68			38			5			70 - 1.21			72 - 7.24
	$prob4$ (median)			68			38			5			--			90 - 8.34
	$prob4$ (hardest)			68			38			5			--			--
	$prob5$ (easiest)			100			58			5			294 - 5.29			0 - 2.42
	$prob5$ (median)			100			58			5			96106 - 522.64			99 - 2.81
	$prob5$ (hardest)			100			58			5			--			104 - 13.45

Table 6 reports results from a total of 50 instances created using five different constraint graph topologies. All variables have domains of 20 or 25 values. The number of allowed tuples for the constraints varied from around 50 for very tight constraints to several thousands for looser ones, according to the frequency separation imposed by parameters $s$ and $s'$ of the separation constraints. These parameters were set at random for each constraint, making sure that very loose constraints were not generated. For example, for a 4-ary basic separation constraint on variables with domain size 20, $s$ was at least 3 (giving 7920 allowed tuples) and at most 5 (giving 120 allowed tuples).

$prob1$, $prob2$, and $prob3$ refer to problems having the topologies shown in Figure 11. $prob4$ consists of three groups of variables, similar to the ones of $prob3$, arranged in a chain-like structure. Finally, instances of $prob5$ consist of randomly generated groups of variables; each one having 8-10 variables and 3-5 3-ary to 5-ary constraints. These groups are interconnected according to their topological distance (i.e. constraints are posted on variables of nearby groups). All instances of $prob1$-$prob4$ have fixed topology. For each topology a set of instances was created by changing the type of the constraints. For example, two instances having the topology of $prob1$ may differ in the type of separation constraints (basic or richer) they include. Also, the frequency separations $s$ and $s'$ imposed by a constraint may differ. Instances of $prob5$ may also differ in their constraint graph topology. We report node visits and run times of the easiest, median, and hardest instance for each topology, with respect to the performance of MGAC⁹. The hardest instances were the same for both the encoding and the non-binary representation (except for $prob3$), while the easiest and median instances were sometimes different.

In Table 6 we can see that there can be very substantial differences in favor of the double encoding. Many instances were solvable in the double encoding with no or very little backtracking while MGAC-2001 thrashed. This is mainly due to the large number of interleaved constraints sharing more than one variable, which boosts propagation in the double encoding. The performance of the algorithms seems to be heavily dependent on the topology of the problems. For example, on instances of $prob2$ the non-binary representation was much more efficient than the double encoding. It seems that in this particular class of problems heuristic choices were misled by the propagation achieved in the double encoding. We have not been able to come up with a satisfactory explanation as to why this occurred in this particular topology.

Table 7: Comparison of algorithms on RLFA problems with separation and adjacent-channel constraints. MAC-hybrid corresponds to a MAC algorithm that runs on the hybrid model.

	problem			$n$			$e$			$arity$			MGAC-2001			MAC-hybrid
													nodes - time			nodes - time
	$prob1$ (easiest)			48			25			8			106 - 20.88			50 - 47.60
	$prob1$ (median)			48			25			8			5078 - 1201.98			84 - 195.43
	$prob1$ (hardest)			48			25			8			--			--
	$prob2$ (easiest)			44			21			8			647 - 192.64			1019 - 308.84
	$prob2$ (median)			44			21			8			80245 - 17690.12			--
	$prob2$ (hardest)			44			21			8			--			--
	$prob5$ (easiest)			100			58			8			76 - 45.92			0 - 22.19
	$prob5$ (median)			100			58			8			22785 - 3230.47			99 - 78.41
	$prob5$ (hardest)			100			58			8			--			18447 - 4233.50

Finally, to investigate the effect that the presence of loose constraints of higher arity has, we run experiments where 8-ary adjacent-channel constraints were posted between variables further apart in the graph, in addition to the separation constraints. In this case using the double encoding to model all the constraints in the problems was infeasible due to the spatial requirements. For example, trying to generate the allowed tuples of a single 8-ary adjacent-channel constraint consumed all the memory of the system. Therefore, we compared algorithm MGAC-2001 on the non-binary model to a MAC algorithm that runs on a hybrid model where the tight separation constraints are modelled using the double encoding and the loose adjacent-channel constraints are kept in the intentional non-binary representation. Table 7 reports results from a total of 30 instances created using the graph topologies of $prob1$, $prob2$ and $prob5$ with the addition of four 8-ary adjacent-channel constraints in each instance. The hybrid model is more efficient on instances of $prob1$ and $prob5$ because of the strong propagation achieved through the binary encoding of the tight constraints. The non-binary model is better on instances of $prob2$ where it seems that propagation through the binary encoding results in bad heuristic choices.