L08: Nesting Inside Sets Flashcards
Which representations can we use to represent nesting within sets?
- Outer Explicit + Inner Explicit
- Outer Explicit + Inner Occurrence
- Outer Occurrence + Inner Occurrence
What is the problem class for nested sets?
Given m,n
Find a cardinality m sets of sets of n digits such
Such that …
What does the explicit-occurrence representation of a set of sets look like? What are its constraints?
We have a 2D matrix with the x axis being the indices for the outer sets (1..m), and the y axis being the domain for the values.
Constraints:
The sum of every column will be n (for fixed cardinality sets).
We can also add a constraint such that the column indices are ordered (lexicographically).
What does the explicit-explicit representation of a set of sets look like? What are its constraints?
We have a 2D matrix with the x axis being the indices for the outer sets (1..m), and the y axis being the indices for the inner sets (1..n).
Constraints:
AllDiff on each column as a number cannot appear twice in a set.
We can also add a constraint such that the column indices are ordered (lexicographically).
We can also have an ascending order of values in each column.
What does the explicit-explicit representation of a set of sets look like? What are its constraints?
We have a 1D matrix indexed by all the possible permutations of a set.
While this is not impossible, it is not feasible for a large n, therefore it is not used.
How can we use occurrence representation to represent relations as sets of tuples?
If we are trying to find the relations between sets A={1,2,3} and B={2,3,4}:
Occurrence representation:
We have a 2D matrix where the axes would be indexed by the values in A and B.
Explicit
How can we use explicit representation to represent relations as sets of tuples?
If we are trying to find the relations between sets A={1,2,3} and B={2,3,4}:
Explicit representation:
We have a 2D matrix where the x axes is indexed by the maximum number of tuples (9 in this case), and the y axis is indexed by 1 and 2, one row for each value in the relation.
The domain for row 1 is A, and the domain for row 2 is B.
What is a viewpoint?
A set of decision variables and domains sufficient to characterise the problem.
Why is viewpoint selection important?
If we make the wrong choice, writing down the constraints can be very awkward, probably leading to poor solving behaviour.
What if a viewpoint makes expressing some of the constraints easy?
We might want to keep this viewpoint and use auxiliary variables to express the remaining constraints.
What is an auxiliary variable?
These extra variables are auxiliary in the sense that they are not needed to characterise the problem.
How are auxiliary variables used in the Golomb Ruler problem?
While it is easy to ensure that there are no 2 ticks in the same position using AllDiff, it is harder to ensure that the distances are also unique.
Therefore, we can use an auxiliary variable to store the differences between every pair of variables.
