-
Notifications
You must be signed in to change notification settings - Fork 6
/
gc_lns.ex
99 lines (80 loc) · 3.04 KB
/
gc_lns.ex
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
defmodule LNS.GraphColoring do
@moduledoc false
require Logger
import MinizincSearch
import MinizincUtils
@gc_model resource_file("mzn/graph_coloring.mzn")
## Find optimal solution for Graph Coloring instance using Randomized LNS.
## 'destruction_rate' is a fraction of the vertex coloring (represented in the model
## by 'colors' var) that will be 'destroyed' for the next iteration.
##
def do_lns(data, iterations, destruction_rate, solver_opts \\ [], opts \\ []) do
instance = MinizincInstance.new(@gc_model, data, solver_opts, opts)
result = lns(
instance,
iterations,
fn solution, method, iteration ->
objective = MinizincResults.get_solution_objective(solution)
Logger.info "Iteration #{iteration}: #{objective}-coloring"
[
better_objective_constraint(solution, "chromatic", method),
destroy_colors(
solution[:data]["colors"],
destruction_rate
)
]
end
)
Logger.info "LNS final: #{get_objective(result)}-coloring"
result
end
## Find optimal solution for Graph Coloring instance using adaptive LNS.
## It's the same as Randomized LNS, but the destruction rate gets increased by 'delta' with every iteration.
##
def do_adaptive_lns(data, iterations, initial_rate, delta, solver_opts \\ [], opts \\ []) do
instance = MinizincInstance.new(@gc_model, data, solver_opts, opts)
result = lns(
instance,
iterations,
fn solution, method, iteration ->
destruction_rate = initial_rate + (iteration - 1) * delta
objective = MinizincResults.get_solution_objective(solution)
Logger.info "Iteration #{iteration}: #{objective}-coloring, rate: #{destruction_rate}"
[
better_objective_constraint(solution, "chromatic", method),
destroy_colors(
solution[:data]["colors"],
destruction_rate
)
]
end
)
Logger.info "LNS final: #{get_objective(result)}-coloring"
result
end
defp get_objective(result) do
MinizincResults.get_solution_objective(
MinizincResults.get_last_solution(result)
)
end
def destroy_colors(coloring, rate) do
vertices = destroy(coloring, rate)
## Normalize colors
new_colors = normalize_colors(Enum.map(vertices, fn {c, _v} -> c end))
## Update reduced coloring with new colors
{_old_colors, v} = Enum.unzip(vertices)
new_coloring = Enum.zip(new_colors, v)
## Generate constraints for the partial coloring
list_to_lns_constraints("colors", new_coloring)
end
## Because of the way the model we use works,
## the colors assigned to vertices are not sequentially enumerated.
## For example, the only 2 colors could have numbers 6 and 11.
## To avoid clashes with model's objective, we will relabel colors,
## i.e., [6, 11] -> [0, 1]
def normalize_colors(colors) do
color_set = MapSet.new(colors)
|> MapSet.to_list
Enum.map(colors, fn c -> Enum.find_index(color_set, fn x -> x == c end) end)
end
end