L09: Multiple Viewpoints Flashcards
Why might we need multiple viewpoints?
Sometimes, the auxiliary variables in are not enough to constitute a viewpoint, therefore it can be useful to have 2 or more full viewpoints.
What is chanelling?
Channeling is linking variables so that changes in one immediately impact another, ensuring they stay consistent and solve problems more efficiently. Channeling prevents conflicting assignments.
The assignments of variables in different viewpoints and auxiliary variables are consistent.
What are branching variables?
The subset of the variable we choose to search over are the branching variables.
We must make sure that assigning the selected branching variables is sufficient to produce a solution.
What are implied constraints?
Logical consequences of the initial specification of the problem.
I.e., there is a chain of reasoning that allows us to deduce implied constraints from initial constraints.
E.g., D1, D2, D3 = {1..9}
If we know that:
x1 + x2 = x3
x1 ≠ x2
Then the following is implied:
x3≥3
Why do we need implied constraints?
If constraint propagation were all-powerful, constraint solver would be able to “see” these logical consequences.
By recording useful logical consequences in the form of new constraints, we help the constraint solver to reduce search.
How do we generate implied constraints?
By hand.
The generation of some of the best implied constraints involves complex reasoning steps which is difficult to automate.
Compare implied constraints with redundant constraints.
We say a constraint is redundant if it is implied by the initial problem specification, but does not reduce search.
We want to avoid such constraints because they just add overhead to the solver and slow the solving process down.
This is another example of why we have to consider the solving process when modelling.
Are symmetry breaking constraints implied?
No.
We know that symmetry-breaking constraints are not implied.
When we break symmetry, we have a new problem- for which new constraints are implied.
Many of the most powerful implied constraints are derived from symmetry breaking.
The CSP obtained by breaking symmetry is not equivalent to the original.
How can we break symmetry in the BIBD problem?
Lex order rows and columns
