cycle
cycle |
Purpose
The cycle constraint ensures that the graph implicitly represented by a set of variables (= nodes) and their domains (= possible successors of a node) contains no sub-tours, that is, tours visiting only a subset of the nodes. The constraint can take an optional second set of variables Preds, representing the inverse relation of the Succ function and ensure the following equivalences:
succi = j ⇒ predj = i for all i and j. Another optional parameter of the cycle constraint allows to take into account an accumulated quantity along the tour such as distance, time or weight. More formally, it ensures the following constraint:
quantity = ∑i,j distmatrixij for all arcs i→j belonging to the tour.
Synopsis
function cycle(succ:array of cpvar) : cpctr
function cycle(succ:array of cpvar, pred:array of cpvar) : cpctr
function cycle(succ:array of cpvar, dist:cpvar, distmatrix:array(range,range) of integer) : cpctr
function cycle(succ:array of cpvar, pred:array of cpvar, dist:cpvar, distmatrix:array(range,range) of integer) : cpctr
Arguments
|
succ
|
the list of successors variables
|
|
pred
|
the list of predecessors variables
|
|
dist
|
the accumulated quantity variable
|
|
distmatrix
|
a (nodes × nodes) matrix of integers representing the quantity to add to the accumulated quantity variable when an edge (i,j) belongs to the tour.
|
Return value
A cycle constraint
Example
To illustrate the cycle constraint we show an implementation of the Traveling Salesman Problem (TSP). The objective of the Traveling Salesman Problem (TSP) is to find the shortest tour through a given set of cities that visits each city exactly once (a Hamiltonian tour). More formally, given a set of n points and a distance between every pair of points, a solution to the TSP is a path of N edges, with identical first and last vertices, containing all n points and with minimal total length. This problem can be modeled as follows: a solution is represented by a function Succ associating with each node its immediate successor. We use an array of N variables 'succ(i)' (one for each city
i∈{0,...,N-1}) to represent the next city visited after city number i where the domain of the variables succ(i) is set to
{0,...,N-1} - {i}.
model "TSP"
uses "kalis"
parameters
S = 14 ! Number of cities to visit
end-parameters
declarations
TC : array(0..3*S) of integer
end-declarations
! TSP DATA
TC :: [
1 , 1647, 9610,
2 , 1647, 9444,
3 , 2009, 9254,
4 , 2239, 9337,
5 , 2523, 9724,
6 , 2200, 9605,
7 , 2047, 9702,
8 , 1720, 9629,
9 , 1630, 9738,
10, 1405, 9812,
11, 1653, 9738,
12, 2152, 9559,
13, 1941, 9713,
14, 2009, 9455]
forward procedure print_solution
setparam("KALIS_DEFAULT_LB", 0)
setparam("KALIS_DEFAULT_UB", S-1)
declarations
CITIES = 0..S-1 ! Set of cities
succ: array(CITIES) of cpvar ! Array of successor variables
prev: array(CITIES) of cpvar ! Array of predecessor variables
end-declarations
setparam("KALIS_DEFAULT_UB", 10000)
declarations
dist_matrix: array(CITIES,CITIES) of integer ! Distance matrix
totaldist: cpvar ! Total distance of the tour
succpred: cpvarlist ! Variable list for branching
end-declarations
! Setting the variable names
forall(p in CITIES) do
setname(succ(p),"succ("+p+")")
setname(prev(p),"prev("+p+")")
end-do
! Add succesors and predecessors to succpred list for branching
forall(p in CITIES) succpred += succ(p)
forall(p in CITIES) succpred += prev(p)
! Build the distance matrix
forall(p1,p2 in CITIES | p1<>p2)
dist_matrix(p1,p2) := round(sqrt((TC(3*p2+1) - TC(3*p1+1)) *
(TC(3*p2+1) - TC(3*p1+1)) + (TC(3*p2+2) - TC(3*p1+2)) *
(TC(3*p2+2) - TC(3*p1+2))))
! Set the name of the distance variable
setname(totaldist, "total_distance")
! Posting the cycle constraint
cycle(succ, prev, totaldist, dist_matrix)
! Print all solutions found
cp_set_solution_callback("print_solution")
! Set the branching strategy
cp_set_branching(assign_and_forbid("bestregret", "bestneighbor",
succpred))
setparam("KALIS_MAX_COMPUTATION_TIME", 5)
! Find the optimal tour
if (cp_minimize(totaldist)) then
if getparam("KALIS_SEARCH_LIMIT")=KALIS_SLIM_BY_TIME then
writeln("Search time limit reached")
else
writeln("Done!")
end-if
end-if
!---------------------------------------------------------------
! **** Solution printing ****
procedure print_solution
writeln("TOUR LENGTH = ", getsol(totaldist))
thispos:=getsol(succ(0))
nextpos:=getsol(succ(thispos))
write(" Tour: ", thispos)
while (nextpos <> getsol(succ(0))) do
write(" -> ", nextpos)
thispos:=nextpos
nextpos:=getsol(succ(thispos))
end-do
writeln
end-procedure
!---------------------------------------------------------------
! **** Variable choice ****
function bestregret(Vars: cpvarlist): integer
! Get the number of elements of "Vars"
listsize:= getsize(Vars)
minindex := 0
mindist := 0
! Set on uninstantiated variables
forall(i in 1..listsize) do
if not is_fixed(getvar(Vars,i)) then
if (i <= S) then
bestn := getlb(getvar(Vars,i))
v:=bestn
mval:=dist_matrix(i-1,v)
while (v < getub(getvar(Vars,i))) do
v:=getnext(getvar(Vars,i),v)
if dist_matrix(i-1,v)<=mval then
mval:=dist_matrix(i-1,v)
bestn:=v
end-if
end-do
sbestn := getlb(getvar(Vars,i))
mval2:= 10000000
v:=sbestn
if (dist_matrix(i-1,v)<=mval2 and v <> bestn) then
mval2:=dist_matrix(i-1,v)
sbestn:=v
end-if
while (v < getub(getvar(Vars,i))) do
v:=getnext(getvar(Vars,i),v)
if (dist_matrix(i-1,v)<=mval2 and v <> bestn) then
mval2:=dist_matrix(i-1,v)
sbestn:=v
end-if
end-do
else
bestn := getlb(getvar(Vars,i))
v:=bestn
mval:=dist_matrix(v,i-S-1)
while (v < getub(getvar(Vars,i))) do
v:=getnext(getvar(Vars,i),v)
if dist_matrix(v,i-S-1)<=mval then
mval:=dist_matrix(v,i-S-1)
bestn:=v
end-if
end-do
sbestn := getlb(getvar(Vars,i))
mval2:= 10000000
v:=sbestn
if (dist_matrix(v,i-S-1)<=mval2 and v <> bestn) then
mval2:=dist_matrix(v,i-S-1)
sbestn:=v
end-if
while (v < getub(getvar(Vars,i))) do
v:=getnext(getvar(Vars,i),v)
if (dist_matrix(v,i-S-1)<=mval2 and v <> bestn) then
mval2:=dist_matrix(v,i-S-1)
sbestn:=v
end-if
end-do
end-if
dsize := getsize(getvar(Vars,i))
rank := integer(10000/ dsize +(mval2 - mval))
if (mindist<= rank) then
mindist := rank
minindex := i
end-if
end-if
end-do
returned := minindex
end-function
!---------------------------------------------------------------
! **** Value choice: choose value resulting in smallest distance
function bestneighbor(x: cpvar): integer
issucc := false
idx := -1
forall (i in CITIES)
if (is_same(succ(i),x)) then
idx:= i
issucc := true
end-if
forall (i in CITIES)
if (is_same(prev(i),x)) then
idx:= i
end-if
if issucc then
returned:= getlb(x)
v:=getlb(x)
mval:=dist_matrix(idx,v)
while (v < getub(x)) do
v:=getnext(x,v)
if dist_matrix(idx,v)<=mval then
mval:=dist_matrix(idx,v)
returned:=v
end-if
end-do
else
returned:= getlb(x)
v:=getlb(x)
mval:=dist_matrix(v,idx)
while (v < getub(x)) do
v:=getnext(x,v)
if dist_matrix(v,idx)<=mval then
mval:=dist_matrix(v,idx)
returned:=v
end-if
end-do
end-if
end-function
end-model
Related topics