Radio link frequency assignment problem

Back to Tutorials | Use cases

Brief description

The problem consists in assigning frequencies to radio communication links in such a way that no interferences occur. Domains are set of integers (non-necessarily consecutive).

Two types of constraints occur:

• (I) the absolute difference between two frequencies should be greater than a given number d_i ( | x - y | > d_i )

• (II) the absolute difference between two frequencies should exactly be equal to a given number d_i ( | x - y | = d_i ).

Different deviations d_i, i in 0..4, may exist for the same pair of links. d_0 corresponds to hard constraints while higher deviations are soft constraints that can be violated with an associated cost a_i. Moreover, pre-assigned frequencies may be known for some links which are either hard or soft preferences (mobility cost b_i, i in 0..4). The goal is to minimize the weighted sum of violated constraints.

So the goal is to minimize the sum:

a_1*nc1+…+a_4*nc4+b_1*nv1+…+b_4*nv4

where nci is the number of violated constraints with cost a_i and nvi is the number of modified variables with mobility cost b_i.

Cabon, B., de Givry, S., Lobjois, L., Schiex, T., Warners, J.P. Constraints (1999) 4: 79.

CFN model

We create N variables for every radio link with a given integer domain. Hard and soft binary cost functions express interference constraints with possible deviations with cost equal to a_i. Unary cost functions are used to model mobility costs with cost equal to b_i. The initial upper bound is defined as 1 plus the total cost where all the soft constraints are maximally violated (costs a_4/b_4).

Data

Original data files can be downloaded from the cost function library FullRLFAP. Their format is described here. You can try a small example CELAR6-SUB1 (var.txt, dom.txt, ctr.txt, cst.txt) with optimum value equal to 2669.

Python model

The following code solves the corresponding cost function network using the pytoulbar2 library and needs 4 arguments: the variable file, the domain file, the constraints file and the cost file (e.g. “python3 rlfap.py var.txt dom.txt ctr.txt cst.txt”).

rlfap.py

import sys
import pytoulbar2

class Data:
	def __init__(self, var, dom, ctr, cst):
		self.var = list()
		self.dom = {}
		self.ctr = list()
		self.cost = {}
		self.nba = {}
		self.nbb = {}
		self.top = 1
		self.Domain = {}

		stream = open(var)
		for line in stream:
			if len(line.split())>=4:
				(varnum, vardom, value, mobility) = line.split()[:4]
				self.Domain[int(varnum)] = int(vardom)
				self.var.append((int(varnum), int(vardom), int(value), int(mobility)))
				self.nbb["b" + str(mobility)] = self.nbb.get("b" + str(mobility), 0) + 1
			else:
				(varnum, vardom) = line.split()[:2]
				self.Domain[int(varnum)] = int(vardom)
				self.var.append((int(varnum), int(vardom)))
		stream = open(dom)
		for line in stream:
			domain = line.split()[:]
			self.dom[int(domain[0])] = [int(f) for f in domain[2:]]

		stream = open(ctr)
		for line in stream:
			(var1, var2, dummy, operand, deviation, weight) = line.split()[:6]
			self.ctr.append((int(var1), int(var2), operand, int(deviation), int(weight)))
			self.nba["a" + str(weight)] = self.nba.get("a" + str(weight), 0) + 1
			
		stream = open(cst)
		for line in stream:
			if len(line.split()) == 3:
				(aorbi, eq, cost) = line.split()[:3]
				if (eq == "="):
					self.cost[aorbi] = int(cost)
					self.top += int(cost) * self.nba.get(aorbi, self.nbb.get(aorbi, 0))

		            
#collect data           
data = Data(sys.argv[1], sys.argv[2], sys.argv[3], sys.argv[4])

top = data.top
Problem = pytoulbar2.CFN(top)

#create a variable for each link
for e in data.var:
	domain = []
	for f in data.dom[e[1]]:
		domain.append('f' + str(f))
	Problem.AddVariable('link' + str(e[0]), domain)

#binary hard and soft constraints
for (var1, var2, operand, deviation, weight) in data.ctr:
	ListConstraints = []
	for a in data.dom[data.Domain[var1]]:
		for b in data.dom[data.Domain[var2]]:
			if ((operand==">" and abs(a - b) > deviation) or (operand=="=" and abs(a - b) == deviation)):
				ListConstraints.append(0)
			else:
				ListConstraints.append(data.cost.get('a' + str(weight),top))
	Problem.AddFunction(['link' + str(var1), 'link' + str(var2)], ListConstraints)

#unary hard and soft constraints
for e in data.var:
	if len(e) >= 3: 
		ListConstraints = []
		for a in data.dom[e[1]]:
			if a == e[2]:
				ListConstraints.append(0)
			else:
				ListConstraints.append(data.cost.get('b' + str(e[3]),top))
		Problem.AddFunction(['link' + str(e[0])], ListConstraints)

#Problem.Dump('rlfap.cfn')
Problem.CFN.timer(300)
res = Problem.Solve(showSolutions=3)
if res:
	print("Best solution found with cost:",int(res[1]),"in", Problem.GetNbNodes(), "search nodes.")
else:
	print('Sorry, no solution found!')