Constraint programming
35 flashcards · Computer Science · by Daniel Vente
what is an exitensional representation?
The representation of a CSP in table form, listing all of the combinations of allowed assignements
List 2 common patterns of CSP moddeling
sequences sets
How can we find solutions to unbounded CSPs?
impose an arbitrary bound in our model, explore that space and continually increase that bound until we find a solution
define a viewpoint
A choice of decision variables and their domains that define a solution to the problem
Name two common ways of modelling a set and explain how they work
Explicit. an array containing the elements present in the set. has lot's of symmetries so usually chosen in ascending order Occurrence an array of possible elements together with a binary variable indicating whether it is in the set or not.
Explain why symmetry in a model can be bad
it can lead to a lot of double or wasted effort by the solver lowering performance
name two common cases of symmetry and explain what they mean
Variable A bijection in terms of variables (i.e. 4Queens) Value A bijection in terms of values (graph colouring)
Explain what a lex-lader is and what it is used for
A collection of lexographic used to brake symmetry. this is done by adding a lexographic ordering constraint per symmetry
explain how a lex squared ordering works
Name advantages of implied constraints and auxilary variables
They can help the solver spot dead ends earlier by requireing it to do less propogation
Give an example of auxiliary variables and channelling constraints
In the Golomb ruler problem, the auxilary variables are the distances and the channeling constraint is that dij = t[i] - t[j]
Explain the difference between d-way branching and 2-way branching
in d-way branching we enumerate all of the elements in a domain directly. in 2-way branching we branch on every variable for every value, one branch representing the variable being equal to that value and the other representing the variable not being equal to that value
Explain what a variable order is and give several examples
The order in which the variables are assigned. This can be fixed (max-deg, lexographic) or dynamic (smallest domain)
what is a dual representation?
A dual representation is a way to represent a constraint problem in terms of binary constraints. Here a dual variable is associated with a constraint and as it's domain it has
Explain why forward checking never has to check backwards
since any inconsistent assignment value will have been removed by the constraint propagation.
define node consistency
node consistency is when all nodes and their associated unary constrains are satisfied with all the values in the domains
define arc consistency
when both nodes of the arc are node consistent for each value in the domain of the origin there is a value on the domain of the destination such that that tuple satisfies the constraint.
define the support of a value w.r.t. an arc
a value in the other domain such that that tuple satisfies the constraint. This is evidence that that value should not be removed from the domain
name the three Geelen's value-heuristics
min conflict cruciality promise
why do people often prefer AC3 over AC4 eventhough AC3 has worse worst case complexity
because AC4 always reaches it's worst complexity whereas AC3 doesn't necessarily and AC3 is hecking easier to implement
Name the time and space complexity of AC4
AC4 time: O(ed^2) AC4 space: O(ed^2)
Name the time and space complexity of AC3
AC3 space: O(e+nd) AC3 time: O(ed^3)
Explain the difference between AC3 and AC2001/3.1
While AC3 checks all the vales in the domain of the destination variable, AC2001 maintains a datastructure of the last found supporting value and continues from there, so it only has to check each future domain once per value
Explain why conflict-learning cannot be used with MAC
Because MAC does a chain of reasoning so the whiped out variable is not adjacent to the assigned variable, making it impossible to tell which variable is at fault for the conflict
Describe the nFC0 algorithm and what it is used for
it is used in non-binary constraint problems (i.e. teriary etc). After an assignement for x_i, make the constraints involving x_i one future and an number of past variables consistent in one pass.
define path consistency
a contraint c(x_i,x_j) is path consistent w.r.t. a thid variable is for every pain <d_j,d_j> satisfyig the constraint there exists d_k in D_k such that <d_i,d_k> satifies c(x_i,x_k) and <d_j,d_k> satisfies c(x_j,x_k).
does path consistency imply arc consistency?
no
define K-Consistency
Giveen assignements to k-1 variables satisfying all constraints amoung them we can choose an assignement to the kth variable such that constraints amounc all k variables are satisfied
define strong K consistency
j-consistent for all 1 <= j<= k
Explain the difference between strong 3-Consistency and strong path consistency
while strong path consistency is only defined for bianry csps, strong 3-consistency is defined for all CSPs, otherwise they are equivalent.
Give a sufficient condition for backtrack-free search, and why this is more expensive than one would expect
for a CSP graph of width $j$, if strong $j+1$ - consistency is enforced the search will be backtrack free. Enforcing k-consistency can change the width of the graph.
define Generalised arc consistency
a constraint c(x_1,...,x_k) is generalised arc consistent if for every variable, there exists a supporting tuple for every element of that variables, domain. A supporting tuple is a tuple that would support that assignment to that variable.
define Bound(D)-consistency
same as GAC but only the bounds are supported, not individual elements.
define Bound(Z)-consistency
same as Bound(Z)-consistency only here the supporting tuple need not be in the domain, just an integer between the two bounds
what is the difference between a coarse-grained and a fine-grained algorithm
Coarse-grained: Only keeps track of which arcs to revise fine-grained: also keeps track of individual domain elements that have been revised.