-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmain.jl
More file actions
149 lines (137 loc) · 6.43 KB
/
Copy pathmain.jl
File metadata and controls
149 lines (137 loc) · 6.43 KB
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
include("readfile.jl")
include("heuristic.jl")
include("metaheuristics.jl")
include("get_opts_values.jl")
include("tabu_search.jl")
using Profile
using CSV
using DataFrames
using OrderedCollections
using ProgressMeter
using Base.Threads
function main(instances_folder = "./gap_1_12", minimization=false)
my_lock = ReentrantLock()
opts = Dict{String,Int32}()
min_factor = 2*(1 - minimization)-1
max_run_time = 8*60
nb_iterations = 20
if instances_folder == "./gap_1_12"
all_opts = getOpts_max()
number_of_instances_per_file = 5
elseif instances_folder == "./gap_abcd"
all_opts = getOpts_min()
number_of_instances_per_file = 6
else
number_of_instances_per_file = 1
all_opts = nothing
end
instance_names = readdir(instances_folder)
name_instances = []
opt_instances = []
best_initial_cost = []
best_initial_heuristic = []
sol_values = []
times = []
gaps = []
best_final_heuristic = []
for name in instance_names
println("###############")
println(name)
for j in 1:number_of_instances_per_file
# Reading the files
println("Instance $j")
readfile("$instances_folder/$name", j-1, minimization)
bound = min_factor*upper_bound(c)
if all_opts != nothing
opt = all_opts["$(name)_$(j)"]
else
opt = bound
end
append!(name_instances, ["$(name)_$(j)"])
append!(opt_instances, [opt])
start_time = time()
# Multi_start
sorted_x, sorted_task_to_agent, sorted_heuristic_names, sorted_costs, sorted_emptiness = multi_start(r, c, b, m, t, 50, true)
if length(sorted_x) == 0
println("No feasible initial solutions")
continue
end
println("$(name)_$(j) : opt $opt, borne $(bound) best_ini $(min_factor*sorted_costs[1])")
append!(best_initial_cost, [sorted_costs[1]])
append!(best_initial_heuristic, [sorted_heuristic_names[1]])
found_optimal = Atomic{Bool}(false)
best_cost_all_methods = sorted_costs[1]
best_heuristic = sorted_heuristic_names[1]
best_gap = round.(abs(opt - min_factor*best_cost_all_methods)/opt*100, digits=2)
@threads for idx in 1:length(sorted_x)
if found_optimal[]
break
end
if (time() - start_time > max_run_time) || (min_factor*best_cost_all_methods == opt)
found_optimal[] = true
break
end
x = sorted_x[idx]
task_to_agent = sorted_task_to_agent[idx]
heuristic_ini = sorted_heuristic_names[idx]
@assert verify_sol(x, r, b)
# First VND
x, task_to_agent, best_cost = variable_neighborhood_descent(r, b, m, t, c, opt, x, task_to_agent,
max_iteration = 1000,
max_elapsed_time = max_run_time - (time() - start_time),
minimization = minimization)
if found_optimal[]
continue
end
# We repeat nb_iterations time a descent and a tabu search
for k in 1:nb_iterations
tabu_len = rand(max(1, floor(Int, 0.2*m)):max(2, floor(Int, 0.5*m)))
x, task_to_agent, best_cost = random_descent_change_agent_or_swap(r, b, m, t, c, opt, x, task_to_agent,
max_iteration = 1000,
max_elapsed_time = max_run_time - (time() - start_time),
minimization = minimization)
@assert verify_sol(x, r, b)
if (min_factor*best_cost == opt) || (time() - start_time >= max_run_time) || found_optimal[]
found_optimal[] = true
break
end
x, task_to_agent, best_cost = tabu_change_and_swap(r, b, m, t, c, tabu_len, opt, x, task_to_agent,
max_iteration=1000,
max_iteration_without_improvement=20,
max_elapsed_time=max_run_time-(time() - start_time),
minimization = minimization)
@assert verify_sol(x, r, b)
if (min_factor*best_cost == opt) || (time() - start_time >= max_run_time ) || found_optimal[]
found_optimal[] = true
break
end
end
@assert cost_sol(c, x) == best_cost
@assert verify_sol(x, r, b)
lock(my_lock) do
if best_cost > best_cost_all_methods
best_cost_all_methods = best_cost
best_heuristic = heuristic_ini
best_gap = round.(abs(opt - min_factor*best_cost_all_methods)/opt*100, digits=2)
end
end
end
total_elapsed_time = time() - start_time
println("Optimum=$opt / final value=$(min_factor*best_cost_all_methods) / gap=$(best_gap)")
append!(sol_values, [best_cost_all_methods])
append!(times, [total_elapsed_time])
append!(gaps, [best_gap])
append!(best_final_heuristic, [best_heuristic])
end
end
df = DataFrame(Instances = name_instances,
Opts = opt_instances,
Best_heuristic_value = best_initial_cost,
Best_heuristic = best_initial_heuristic,
Best_value_found = sol_values,
Gap_to_opt= gaps,
Elapsed_time = times,
Best_start_heuristic = best_final_heuristic)
CSV.write("results/multi_start_tabou.csv", df, delim=';')
end
main()