Information Technology Reference
In-Depth Information
Separation constraints prevent interference between cells which are located
geographically close and which broadcast in each other's area of service. Illegal
channels account for channels reserved for external uses (e.g., for military bases).
The
solution to this problem does not use an assignment and has
a dual interpretation as a formula. We tested this program on various data.
We assume here for simplicity that each
Alma-0
c i equals
i
and each
f i equals
i
,so
C
=
f
1
;:::;ng
and
F
=
f
1
;:::;mg
.
MODULE FrequencyAssignment;
CONST N = 30;
(* number of cells *)
M = 27;
(* number of frequencies *)
TYPE SeparationMatrix = ARRAY [1..N],[1..N] OF INTEGER;
IllegalFrequencies = ARRAY [1..N],[1..M] OF BOOLEAN;
Assignment = ARRAY [1..N] OF [1..M];
(* solution vector *)
VAR S: SeparationMatrix;
F: IllegalFrequencies;
A: Assignment;
noSol: INTEGER;
PROCEDURE AssignFrequencies(S: SeparationMatrix; F: IllegalFrequencies;
VAR A: Assignment);
VAR i, j, k: INTEGER;
BEGIN
FORi:=1TONDO
SOME j := 1 TO M DO (* j is a candidate frequency for cell i *)
NOT F[i,j];
FOR k := 1 TO i-1 DO
abs(A[k] - j) >= S[k,i]
END;
A[i] = j
END
END
END AssignFrequencies;
BEGIN
InitializeData(S,F);
AssignFrequencies(S,F,A);
PrintSolution(A)
END FrequencyAssignment.
The simple code of the procedures InitializeData and PrintSolution is
omitted. The generalized equality A[i] = j serves here as an assignment and
the SOME statement takes care of automatic backtracking in the search for the
right frequency j .
In the second part of the paper we shall discuss an alternative solution to
this problem using constraints.
Search WWH ::




Custom Search