(!****************************************************************
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
LINKS = 1..18 ! Range of links between nodes
DEM: array(NODES) of integer ! Demand of nodes
LINK: array(LINKS,1..2) of integer ! Neighboring 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
forall(l in LINKS)
all_different(
union(d in INDEX(LINK(l,1))..INDEX(LINK(l,1))+DEM(LINK(l,1))-1) {use(d)} +
union(d in INDEX(LINK(l,2))..INDEX(LINK(l,2))+DEM(LINK(l,2))-1) {use(d)},
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
|
(!****************************************************************
CP example problems
===================
file freqas_graph.mos
`````````````````````
Frequency assignment problem from telecommunications.
- Solution graph drawing-
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. Sep. 2018
*****************************************************************!)
model "Frequency assignment"
uses "kalis", "mmsvg"
forward public procedure print_solution
forward procedure draw_solution
declarations
NODES = 1..10 ! Range of nodes
LINKS = 1..18 ! Range of links between nodes
DEM: array(NODES) of integer ! Demand of nodes
LINK: array(LINKS,1..2) of integer ! Neighboring 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
forall(l in LINKS)
all_different(
union(d in INDEX(LINK(l,1))..INDEX(LINK(l,1))+DEM(LINK(l,1))-1) {use(d)} +
union(d in INDEX(LINK(l,2))..INDEX(LINK(l,2))+DEM(LINK(l,2))-1) {use(d)},
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
draw_solution
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
draw_solution
cp_show_stats
elif sol>0 then
writeln("Optimality proven")
else
writeln("Problem has no solution")
end-if
svgwaitclose("Close browser window to terminate model execution.", 1)
!********************************************************************
! **** 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
! **** Solution drawing ****
procedure draw_solution
declarations
GraphFreq: array(range) of integer
X,Y: array(NODES) of real ! Coordinates of nodes
end-declarations
N:= getsize(NODES)
forall(n in NODES) do
X(n):= N/2*(cos(M_PI/3+1.2*n*M_PI/N))
Y(n):= (getsol(numfreq)+1)/2*(1+sin(M_PI/3+1.2*n*M_PI/N))
end-do
! Draw different color graph per frequency
forall (f in 1..getsol(numfreq)) do
svgaddgroup("G"+f, "Frequency "+f)
svgaddtext(3, f, "Freq "+f)
end-do
forall(n in NODES, d in INDEX(n)..INDEX(n)+DEM(n)-1)
svgaddline("G"+getsol(use(d)), X(n), Y(n), 3, getsol(use(d)))
! Graph representing nodes and links between nodes
svgaddgroup("N", "Network", SVG_BLACK)
svgsetstyle("text-anchor", "end")
forall(l in LINKS)
svgaddline(X(LINK(l,1)), Y(LINK(l,1)), X(LINK(l,2)), Y(LINK(l,2)))
forall(n in NODES) svgaddtext(X(n),Y(n), "Node "+n)
svgsetgraphviewbox(-N/2-2,-1,N+5,N+5)
svgsetgraphscale(25)
svgrefresh
end-procedure
end-model
|
