 FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home   Frequency assignment problem

Description
Frequency assignment problem: 'abs', 'distance', and 'all-different' constraints; branching strategy for variables; solution callback; interrupting and restarting the search.

Further explanation of this example: 'Xpress Kalis User Guide', Section 3.4 abs and distance: Frequency assignment

Source Files

freqasgn.mos

```(!****************************************************************
CP example problems
===================

file freqasgn.mos
`````````````````
Frequency assignment problem from telecommunications.

We are given a network of cells (nodes) with requirements of
discrete frequency bands. Each cell has a demand of a number of
frequencies (bands).
The objective is to minimize the number of frequencies used in
the network so that
(1) Neighboring nodes all use different frequencies (interference).
(2) If a cell uses several frequencies they must all be different
by at least 2.

*** This model cannot be run with a Community Licence
for the provided data instance ***

(c) 2008 Artelys S.A. and Fair Isaac Corporation
Creation: 2005, rev. Mar. 2013
*****************************************************************!)

model "Frequency assignment"
uses "kalis"

forward public procedure print_solution

declarations
NODES = 1..10                               ! Range of nodes
DEM: array(NODES) of integer                ! Demand of nodes
INDEX: array(NODES) of integer              ! Start index in 'use'
NUMDEM: integer                             ! Upper bound on no. of freq.
end-declarations

DEM :: (1..10)[4, 5, 2, 3, 2, 4, 3, 4, 3, 2]
LINK:: (1..18,1..2)[1, 3, 1, 4, 1, 6,
2, 4, 2, 7,
3, 4, 3, 6, 3, 8, 3, 9,
4, 7, 4, 9, 4,10,
5, 7, 5, 8, 5, 9,
6, 9, 7, 8, 8,10]
NUMDEM:= sum(n in NODES) DEM(n)

! Correspondence of nodes and demand indices:
! use(d) d = 1, ..., DEM(1) correspond to the demands of node 1
!            d = DEM(1)+1, ..., DEM(1)+DEM(2))     - " -     node 2  etc.
INDEX(1):= 1
forall(n in NODES | n > 1) INDEX(n) := INDEX(n-1) + DEM(n-1)

declarations
DEMANDS = 1..NUMDEM                         ! Range of frequency demands
use: array(DEMANDS) of cpvar                ! Frequency used for a demand
numfreq: cpvar                              ! Number of frequencies used
Strategy: array(range) of cpbranching
end-declarations

! Setting the domain of the decision variables
forall(d in DEMANDS) setdomain(use(d), 1, NUMDEM)

! All frequencies attached to a node must be different by at least 2
forall(n in NODES, c,d in INDEX(n)..INDEX(n)+DEM(n)-1 | c<d)
distance(use(c), use(d)) >= 2
!  abs(use(c) - use(d)) >= 2

! Neighboring nodes take all-different frequencies
all_different(
KALIS_GEN_ARC_CONSISTENCY)

! Objective function: minimize the number of frequencies used, that is,
! minimize the largest value assigned to 'use'
setname(numfreq, "NumFreq")
numfreq = maximum(use)

! Search strategy
Strategy(1):=assign_var(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX, use)
Strategy(2):=assign_var(KALIS_MAX_DEGREE, KALIS_MIN_TO_MAX, use)
cp_set_branching(Strategy(1))
setparam("KALIS_MAX_COMPUTATION_TIME", 1)
cp_set_solution_callback("print_solution")

! Try to find solution(s) with strategy 1
if (cp_minimize(numfreq)) then
cp_show_stats
sol:=getsol(numfreq)
end-if

! Restart search with strategy 2
cp_reset_search
if sol>0 then                             ! If a solution was found:
numfreq <= sol-1                         ! Add upper bound on objective
end-if
cp_set_branching(Strategy(2))
setparam("KALIS_MAX_COMPUTATION_TIME", 1000)

if (cp_minimize(numfreq)) then
cp_show_stats
elif sol>0 then
writeln("Optimality proven")
else
writeln("Problem has no solution")
end-if

!********************************************************************
! **** Solution printout ****
public procedure print_solution
writeln("Number of frequencies: ", getsol(numfreq))
writeln("Frequency assignment: ")
forall(n in NODES) do
write("Node ", n, ": ")
forall(d in INDEX(n)..INDEX(n)+DEM(n)-1) write(getsol(use(d)), " ")
writeln
end-do
end-procedure

end-model

```   