I'm working on a project, where I have to solve a GTSP. THe project is about a primeminister that has to visit one city in every electorate (cluster) and has to start and end at city 1.
I have 17 different cities and 5 clusters (without city 1). As of now I have written the following in Julia, but it doesnt seem to give me a corract answer, as I start by going from edge 1 to 1.. (see the output at the bottom)
I know I'm missing some constraints, but as of now I feel like I have tried everything, at it doesn't seem to work. Do you have any tips on constraints missing?
using JuMP
using GLPK
m = Model(GLPK.Optimizer)
n=17
cost = [0 506 635 91 385 155 110 130 490 368 154 68 610 641 471 265 255;
506 0 355 415 585 475 480 500 605 320 380 440 360 235 81 480 440;
635 355 0 602 390 495 560 531 295 675 640 575 705 585 435 420 755;
91 415 602 0 347 118 75 94 457 280 63 27 520 550 380 232 235;
385 585 390 347 0 240 305 276 120 590 410 320 835 745 575 125 582;
155 475 495 118 240 0 65 36 350 365 181 91 605 610 440 125 353;
110 480 560 75 305 65 0 29 415 348 138 48 590 625 455 190 310;
130 500 531 94 276 36 29 0 386 367 157 67 610 635 465 161 329;
490 605 295 457 120 350 415 386 0 625 520 430 865 770 600 230 680;
368 320 675 280 590 365 348 367 625 0 240 300 250 285 245 475 150;
154 380 640 63 410 181 138 157 520 240 0 90 480 515 345 295 175;
68 440 575 27 320 91 48 67 430 300 90 0 545 577 407 205 262;
610 360 705 520 835 605 590 610 865 250 480 545 0 190 295 715 400;
641 235 585 550 745 610 625 635 770 285 515 577 190 0 170 645 435;
471 81 435 380 575 440 455 465 600 245 345 407 295 170 0 475 385;
265 480 420 232 125 125 190 161 230 475 295 205 715 645 475 0 467;
255 440 755 235 582 353 310 329 680 150 175 262 400 435 385 467 0]
c1 = [13,14]
c2 = [5,9,16]
c3 = [4,6,7,8,11,12,17]
c4 = [3]
c5 = [2, 10, 15]
c = [c1, c2, c3, c4, c5]
#variable definition
@variable(m, x[1:n,1:n], Bin)
@variable(m, u[1:n])
@variable(m, z[1:n], Bin)
#objective function
@objective(m, Min, sum(cost[i, j] * x[i,j] for i = 1:n for j = 1:n))
# constraints - flow out of node
@constraint(m, sum(x[i,j] for j =1:n for i=1) == 1 )
@constraint(m, sum(x[i,j] for j in c5 for i =1:n) == 1)
@constraint(m, sum(x[i,j] for j in c1 for i =1:n) == 1)
@constraint(m, sum(x[i,j] for j in c2 for i =1:n) == 1)
@constraint(m, sum(x[i,j] for j in c3 for i =1:n) == 1)
@constraint(m, sum(x[i,j] for j in c4 for i =1:n) == 1)
#float into cluster
@constraint(m, sum(x[i,j] for j =1 for i = 1:n) == 1)
@constraint(m, sum(x[i,j] for j=1:n for i =c1) == 1)
@constraint(m, sum(x[i,j] for j=1:n for i =c2) == 1)
@constraint(m, sum(x[i,j] for j=1:n for i =c3) == 1)
@constraint(m, sum(x[i,j] for j=1:n for i =c4) == 1)
@constraint(m, sum(x[i,j] for j=1:n for i =c5) == 1)
# constraints - node order
for i=1:n, j=1:n
if i != 1 && j!=1
@constraint(m, u[i]-u[j]+(n-1)*x[i,j] <= (n-2))
end
end
# constraints - bounds on u
@constraint(m, u[1]==1)
@constraint(m, oneposl[i=2:n], u[i]>=2)
@constraint(m, oneposu[i=2:n], u[i]<=n)
optimize!(m)
println("Objective Value: ", JuMP.objective_value(m))
for i=1:n, j=1:n
if JuMP.value(x[i,j]) > 1-1e-6
println("Edge ", i, "-", j, " ", JuMP.value(x[i,j]))
#println("x:", )
end
end
I tried some different constraints, but I can see I need some constraints on the order going into and out of each cluster.
Try adding:
for i=1:n
@constraint(m, sum(x[i,j]-x[j,i] for j=1:n) == 0)
end
These constraints ensure the number of in-edges and out-edges of each node (not cluster) is the same. Without this constraint, the cycle could enter a cluster at one node and exit from a different node.
Also, this constraint:
@constraint(m, oneposu[i=2:n], u[i]<=n)
might need to be:
@constraint(m, oneposu[i=2:n], u[i]<=length(c)+1)
to make sure the timing for each node in the cycle is limited to the length of the cycle. The length of the cycle is the number of clusters.