-
Notifications
You must be signed in to change notification settings - Fork 11
/
FlatZincCompiler.scala
168 lines (141 loc) · 6.58 KB
/
FlatZincCompiler.scala
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package yuck.flatzinc.compiler
import java.util.concurrent.Callable
import yuck.core._
import yuck.flatzinc.FlatZincSolverConfiguration
import yuck.flatzinc.ast.FlatZincAst
import yuck.util.arm.Sigint
import yuck.util.logging.LazyLogger
/**
* @author Michael Marte
*
*/
final class FlatZincCompiler
(ast: FlatZincAst,
cfg: FlatZincSolverConfiguration,
randomGenerator: RandomGenerator,
sigint: Sigint,
logger: LazyLogger)
extends Callable[FlatZincCompilerResult]
{
override def call = {
val cc =
if (cfg.preferImplicitSolvingOverDomainPruning) {
try {
preferImplicitSolvingOverDomainPruning
}
catch {
case error: VariableWithInfiniteDomainException =>
logger.log(error.getMessage)
logger.log("Trying again, now with pruning before neighbourhood generation")
preferDomainPruningOverImplicitSolving
}
} else {
preferDomainPruningOverImplicitSolving
}
checkSearchVariableDomains(cc)
assignValuesToDanglingVariables(cc)
logger.criticalSection {
logger.withLogScope("Yuck model statistics") {
logYuckModelStatistics(cc)
}
}
val vars = (for ((key, x) <- cc.vars) yield key.toString -> x).toMap
val arrays = (for ((key, array) <- cc.arrays) yield key.toString -> array).toMap
new FlatZincCompilerResult(
cc.ast, cc.space, vars, arrays, cc.costVar, Option(cc.objectiveVar), cc.objective,
cc.maybeNeighbourhood)
}
private def preferDomainPruningOverImplicitSolving: CompilationContext = {
val cc = new CompilationContext(ast, cfg, logger)
run(new DomainInitializer(cc, randomGenerator.nextGen))
run(new DomainPruner(cc, randomGenerator.nextGen, sigint))
finishCompilation(cc)
cc
}
private def preferImplicitSolvingOverDomainPruning: CompilationContext = {
// The compilation proceeds in three stages:
// The first stage identifies implicit constraints.
// The second stage computes domain reductions.
// The third stage builds the final model where implicit solving takes precedence over domain pruning.
// The purpose of this approach is to take domain reductions into account as far as possible without
// inhibiting implicit solving.
val cc2 = {
// stage 1: identify implicit constraints
val cc1 = new CompilationContext(ast, cfg, logger)
run(new DomainInitializer(cc1, randomGenerator.nextGen))
finishCompilation(cc1)
// stage 2: compute domain reductions
run(new DomainPruner(cc1, randomGenerator.nextGen, sigint))
// stage 3: build final model, taking domain reductions into account as far as possible without
// inhibiting implicit solving
val cc2 = new CompilationContext(ast, cfg, logger)
run(new DomainInitializer(cc2, randomGenerator.nextGen))
for ((a, domain) <- cc1.domains if ! cc1.implicitlyConstrainedVars.contains(cc1.vars(a))) {
cc2.domains += a -> domain
}
cc2.equalVars ++= cc1.equalVars
for (constraint <- cc1.impliedConstraints
if ast.involvedVariables(constraint).map(cc1.vars).intersect(cc1.implicitlyConstrainedVars).isEmpty)
{
cc2.impliedConstraints += constraint
}
// From this point on, we don't need cc1 anymore, so let it go out of scope to free up memory.
cc2
}
// continuation of stage 3
finishCompilation(cc2)
cc2
}
private def finishCompilation(cc: CompilationContext) {
run(new VariableFactory(cc, randomGenerator.nextGen))
run(new VariableClassifier(cc, randomGenerator.nextGen))
run(new ConstraintFactory(cc, randomGenerator.nextGen, sigint))
run(new DomainFinalizer(cc, randomGenerator.nextGen))
run(new ObjectiveFactory(cc, randomGenerator.nextGen))
run(new ConstraintDrivenNeighbourhoodFactory(cc, randomGenerator.nextGen, sigint))
}
// Use the optional root log level to focus on a particular compilation phase.
private def run(phase: CompilationPhase, rootLogLevel: yuck.util.logging.LogLevel = yuck.util.logging.FineLogLevel) {
if (sigint.isSet) {
throw new FlatZincCompilerInterruptedException
}
logger.withRootLogLevel(rootLogLevel) {
logger.withTimedLogScope("Running %s".format(phase.getClass.getSimpleName)) {
phase.run
}
}
}
private def checkSearchVariableDomains(cc: CompilationContext): Unit = {
for (x <- cc.space.searchVariables) {
if (! x.domain.isFinite) {
throw new VariableWithInfiniteDomainException(x)
}
}
}
private def assignValuesToDanglingVariables(cc: CompilationContext) {
for ((key, x) <- cc.vars
if cc.space.isDanglingVariable(x) && ! cc.space.searchState.hasValue(x))
{
if (! x.domain.isFinite) {
throw new VariableWithInfiniteDomainException(x)
}
cc.logger.logg("Assigning random value to dangling variable %s".format(x))
x.assignRandomValue(cc.space, randomGenerator)
}
}
private def logYuckModelStatistics(cc: CompilationContext) = {
lazy val searchVariables = cc.space.searchVariables
logger.logg("Search variables: %s".format(searchVariables))
logger.log("%d search variables".format(searchVariables.size))
lazy val searchVariablesCoveredByNeighbourhood =
cc.maybeNeighbourhood.map(_.searchVariables).getOrElse(Set[AnyVariable]())
logger.logg("Search variables covered by neighbourhood: %s".format(searchVariablesCoveredByNeighbourhood))
logger.log("%d search variables covered by neighbourhood".format(searchVariablesCoveredByNeighbourhood.size))
logger.log("%d channel variables".format(cc.space.channelVariables.size))
lazy val danglingVariables = cc.vars.valuesIterator.filter(cc.space.isDanglingVariable(_)).toSet
logger.logg("Dangling variables: %s".format(danglingVariables))
logger.log("%d dangling variables".format(danglingVariables.size))
logger.log("%d constraints".format(cc.space.numberOfConstraints))
logger.log("%d implicit constraints".format(cc.space.numberOfImplicitConstraints))
}
}