-
Notifications
You must be signed in to change notification settings - Fork 0
/
tsp.jl
104 lines (82 loc) · 2.48 KB
/
tsp.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
using JuMP, Gurobi, PyPlot, DelimitedFiles
num_instances = 10
output_path = ("/home/isabecl/travelling-salesman/")
function read_processing_times(cont)
input_path = ("/home/isabecl/travelling-salesman/instances/")
processing_time_instance = string(input_path,"p", cont, ".txt")
p = readdlm(processing_time_instance, Int)
return(p)
end
function MILP(p)
N = size(p,1)
# Model building
model = Model(optimizer_with_attributes(Gurobi.Optimizer))
# Decision variables
@variable(model, x[1:N,1:N], Bin)
# Objective function
@objective(model, Min, sum(x[i,j]*p[i,j] for i=1:N,j=1:N))
# Constraints
for i=1:N
@constraint(model, x[i,i] == 0)
@constraint(model, sum(x[i,1:N]) == 1)
end
for j=1:N
@constraint(model, sum(x[1:N,j]) == 1)
end
for f=1:N, t=1:N
@constraint(model, x[f,t]+x[t,f] <= 1)
end
status = optimize!(model)
function is_tsp_solved(m,x)
N = size(x)[1]
x_val = JuMP.value.(x)
# find cycle
cycle_idx = Int[]
push!(cycle_idx, 1)
while true
v, idx = findmax(x_val[cycle_idx[end],1:N])
if idx == cycle_idx[1]
break
else
push!(cycle_idx,idx)
end
end
println("cycle_idx: ", cycle_idx)
println("Length: ", length(cycle_idx))
if length(cycle_idx) < N
@constraint(m, sum(x[cycle_idx,cycle_idx]) <= length(cycle_idx)-1)
return false
end
println("cycle_idx: ", cycle_idx)
println("Length: ", length(cycle_idx))
return true, cycle_idx
end
# Solving the model
while !is_tsp_solved(model, x)[1]
status = optimize!(model)
end
cycle = is_tsp_solved(model, x)[2]
zIP = objective_value(model)
tzIP = MOI.get(model, MOI.SolveTime())
return(zIP, tzIP, cycle)
end
# Saving distances in an array
p = Array{Int64,2}[]
for j = 1:num_instances
push!(p, read_processing_times(j))
end
file_name = string(output_path,"results.txt")
results = open(file_name, "w")
println(results,"Instance - Route - Cost ")
close(results)
for j = 1:num_instances
println()
println("MILP model is starting!")
# Running MILP
zIP, tzIP, way = MILP(p[j])
results = open(file_name, "a")
println(results,j," ",way," ",zIP)
close(results)
println(j, ") ","MILP-1 ",zIP," ",tzIP)
end
println("The MILP model was suscefull run!")