-
Notifications
You must be signed in to change notification settings - Fork 10
/
search.jl
84 lines (69 loc) · 3.43 KB
/
search.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
include("dfs.jl")
include("dfwbs.jl")
include("ilds.jl")
include("rbs.jl")
include("lns.jl")
"""
initroot!(toCall::Stack{Function}, ::F, model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection) where F <: SearchStrategy
Initialisation function that fill the toCall Stack according to a certain strategy.
"""
function initroot!(toCall::Stack{Function}, ::F, model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection) where F <: SearchStrategy
throw(ErrorException("Search Strategy $(F) (initroot! function ) not implemented."))
end
"""
search!(model::CPModel, strategy::S, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection=BasicHeuristic(); out_solver::Bool=false) where S <: SearchStrategy
Perform a search following a specific strategy in the `model` using `variableHeuristic` to choose which domain will be changed
at each branching and using `valueSelection` to choose how the branching will be done.
"""
function search!(model::CPModel, strategy::S, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection=BasicHeuristic(); out_solver::Bool=false) where S <: SearchStrategy
tic()
# create env and get first observation
valueSelection(InitializingPhase, model)
toCall = Stack{Function}()
# Starting at the root node with an empty stack
currentStatus = initroot!(toCall, strategy, model, variableHeuristic, valueSelection)
while !isempty(toCall)
# Stop right away if reached a limit
if currentStatus == :NodeLimitStop || currentStatus == :SolutionLimitStop || currentStatus == :TimeLimitStop || currentStatus == :MemoryLimitStop || (out_solver && (currentStatus in [:Infeasible, :FoundSolution]))
break
end
if currentStatus != :SavingState
valueSelection(StepPhase, model, currentStatus) # set reward and metrics
end
currentProcedure = pop!(toCall)
currentStatus::Union{Nothing, Symbol} = currentProcedure(model, currentStatus)
end
# set final reward and last observation
model.statistics.numberOfSolutions=sum(map(x->!isnothing(x),model.statistics.solutions))
valueSelection(EndingPhase, model, currentStatus)
toc()
if currentStatus == :NodeLimitStop || currentStatus == :SolutionLimitStop || currentStatus == :TimeLimitStop || currentStatus == :MemoryLimitStop || (out_solver & (currentStatus in [:Infeasible, :FoundSolution]))
if model.displayXCSP3
if !isnothing(get_index_solution(model))
println("s SATISTFIABLE")
else
println("s UNKNOWN")
end
end
return currentStatus
end
if isa(strategy, DFSearch) && !all(map(x->isnothing(x),model.statistics.solutions)) == 1 # Only the DFS search can give the optimality certificate
if model.displayXCSP3
if !isnothing(model.objective)
println("s OPTIMUM FOUND")
else
println("s SATISTFIABLE")
end
end
return :Optimal
elseif !all(map(x->isnothing(x),model.statistics.solutions)) == 1
if model.displayXCSP3
println("s SATISTFIABLE")
end
return :NonOptimal
end
if model.displayXCSP3
println("s UNSATISFIABLE")
end
return :Infeasible
end