-
Notifications
You must be signed in to change notification settings - Fork 10
/
dfwbs.jl
78 lines (68 loc) · 3.37 KB
/
dfwbs.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
"""
initroot!(toCall::Stack{Function}, ::DFWBSearch, model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection)
Used as a generic function to instantiate the research based on a specific Strategy <: SearchStrategy.
"""
function initroot!(toCall::Stack{Function}, ::DFWBSearch, model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection)
return expandDfwbs!(toCall, model, variableHeuristic, valueSelection, direction= :Left)
end
"""
expandDfwbs!(toCall::Stack{Function}, model::CPModel, variableHeuristic::Function, valueSelection::ValueSelection, newConstraints=nothing)
Expands the DFWBS search tree.
"""
function expandDfwbs!(toCall::Stack{Function}, model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection, newConstraints=nothing; prunedDomains::Union{CPModification,Nothing}=nothing, direction::Symbol)
# Dealing with limits
model.statistics.numberOfNodes += 1
model.statistics.numberOfNodesBeforeRestart += 1
if !belowTimeLimit(model)
return :TimeLimitStop
end
if !belowMemoryLimit(model)
return :MemoryLimitStop
end
if !belowNodeLimit(model)
return :NodeLimitStop
end
if !belowSolutionLimit(model)
return :SolutionLimitStop
end
feasible, pruned = fixPoint!(model, newConstraints, prunedDomains; isFailureBased=isa(variableHeuristic, FailureBasedVariableSelection))
updateStatistics!(model,pruned)
if !feasible
model.statistics.numberOfInfeasibleSolutions += 1
model.statistics.numberOfInfeasibleSolutionsBeforeRestart += 1
return :Infeasible
end
if solutionFound(model)
act = triggerFoundSolution!(model)
if act == :tightenObjective
if isa(valueSelection, LearnedHeuristic) && !valueSelection.trainMode || isa(valueSelection, Union{BasicHeuristic, ImpactHeuristic})
tightenObjective!(model)
end
end
return :FoundSolution
end
if direction == :Right
valueSelection(InitializingPhase, model)
end
x = variableHeuristic(model)
v = valueSelection(DecisionPhase, model, x)
push!(toCall, (model, currentStatus) -> (restoreState!(model.trailer); :BackTracking))
push!(toCall, (model, currentStatus) -> (
prunedDomains = CPModification();
addToPrunedDomains!(prunedDomains, x, remove!(x.domain, v));
expandDfwbs!(toCall, model, variableHeuristic, valueSelection, getOnDomainChange(x); prunedDomains=prunedDomains, direction = :Right)
))
push!(toCall, (model, currentStatus) -> (saveState!(model.trailer); :SavingState))
push!(toCall, (model, currentStatus) -> (restoreState!(model.trailer); :BackTracking))
push!(toCall, (model, currentStatus) -> (
prunedDomains = CPModification();
addToPrunedDomains!(prunedDomains, x, assign!(x, v));
currentStatus = expandDfwbs!(toCall, model, variableHeuristic, valueSelection, getOnDomainChange(x); prunedDomains=prunedDomains, direction = :Left);
if currentStatus != :Feasible
valueSelection(EndingPhase, model, :End)
end;
return currentStatus
))
push!(toCall, (model, currentStatus) -> (saveState!(model.trailer); :SavingState))
return :Feasible
end