L04: Sets Flashcards
Can we have a combined representation?
- Obviously, can have combinations of the two representations (e.g. OA, OB and EC)
- For example the intersection of two occurrence representations is an explicit representation
- Constraints on original sets have to be modelled appropriately
How can we derive a finite domain from an infinite domain for the GRP?
It is possible to generate one feasible solution
- 0, 1, 3, 7, 15, …, (2^n) -1
So every tick must be between 0 and (2^n) -1
We can then modify the model:
- Given a positive integer n
- Find a set of n integer ticks on a ruler, each within 0.. (2^n)-1
- Such that all inter-tick distances are distinct
- Minimising the maximum tick distance
How can we use explicit representation for a bounded-cardinality set without switches?
Instead of using a switches array, we can use a marker.
The marker is a variable that indicates the last index at which an element of the set appears, usually a 0.
The values at all the indexes AFTER THE MARKER will be 0.
Constraints:
- For i in 1..n-1. i+1 ≤ marker -> E[I] < E[i+1]
- For i in 1..n. i > marker -> E[I] = 0
- Sum(E) = s
These constraints say that if the index is less than the marker, then the value is valid (in the part of the array that is valid), this removes the equivalence classes.
Otherwise, we are in the area of the set that is unused, and so the value is assigned to 0.
Again the sum remains unchanged with this representation.
What are some constraints on sets?
- Intersection
- Union
- Subsets
What constraint we can use to remove equivalence for explicit representation for a fixed cardinality set?
- We can choose a canonical element from each class
- The obvious choose is to require an ascending order (all elements must be in ascending order)
What is a fixed-cardinality set?
- Given n and s
- Find a set of n digits that sum to s.
What is a set?
- A collection of distinct objects (no repetition)
- Not arranged in any particular order
- Uses bracket notation
What is an occurrence bounded-cardinality set?
- Given n and s
- Find a set of at most n digits that sum to s
Constraints:
- Sum(O) <= n
- O[1] + 2O[2] + 3O[3] + … + 9O[9] = s
What is an explicit bounded-cardinality set?
- Given n and s
- Find a set of at most n digits that sum to s.
Constraints:
- The switches are in non-ascending order (push 0s to the end)
- For i in 1..n-1
Switches[i+1] ≠ 0 -> E[i] < E[i+1]
- For i in 1..n
Switches[i] = 0 -> E[i] = 0
- Sum(E) = s
Explanation:
We are adding a new array of variables (switches) that are 0 or 1 depending on whether the corresponding index in the set is ‘active’ (whether or not the variable is used in the set). This is because we have a bounded-cardinality set and so we do not know if all the decision variables in the set will be assigned. In this sense, all the ones in the switches array will be at the start and any 0s will be at the end.
What is decomposition in the context of complex constraints?
Complex constraints can be decomposed to simple
constraints, each of which has at most one operator and
possibly one equality sign.
For example
- (A U B) ⊆(C ∩ D)
Can be decomposed into three constraints
- X = A U B
- Y = C ∩ D
- X ⊆ Y
What is occurrence representation in fixed-cardinality sets?
- Given n and s
- Find a set of n digits that sum to s.
Introduce O, an array of decision variables indexed by x (defined domain) where the domain for each variable is {0,1}
Constraints:
- Sum(O) = n (get size of set)
- O[1] + 2O[2] + 3O[3] + … + 9O[9] = s (get sum of set)
This representation does not introduce an equivalence class
What is explicit representation in fixed cardinality sets?
- Given n and s
- Find a set of n digits that sum to s.
Introduce an array E of decision variables indexed 0-n where the domain of each is x (defined domain)
The constraints are:
- AllDifferent(E)
- Sum(E) = s
This representation introduces an equivalence class of assignments
What is the explicit representation of a subset?
Model A ⊆ B
- B is a set of digits
E.g. if the cardinality is 5
- EA, EB will be indexed 1-5 and the domain is 1-n.
We can then use a switch array or a marker:
Using a switch:
- For i in 1..5 . If SA = 1, then EA[i] exists at some index in
EB
Using a marker:
- For i in 1..5 . If i ≤ marker then EA[i] exists at some index in EB
What is the explicit representation of set intersection?
Model A ∩ B = C
- A, B are sets of digits
- We have an array C which tells us the values from A and B that intersect
- A AND B
E.g. if the cardinality is 5
- EA, EB will be indexed 1-5 and the domain is 1-n.
- EC will also be indexed 1-5 as there is a maximum of 5 intersecting values
- If there is a value in A AND B, the value will be stored somewhere in EC
- We need to check vice-versa: if there is a value in EC, then it must also appear in EA AND EB
- We need this constraint for the solver to work correctly
We can then use a switch array or a marker to indicate which if the indices are unused (when not all the values intersect).
What is the explicit representation of set union?
Model A U B = C
- A, B are sets of digits
- We have an array C which tells us the union of values from A and B
- A OR B
E.g. if the cardinality is 5
- EA, EB will be indexed 1-5 and the domain is 1-n.
- EC will also be indexed 1-10 as there is a maximum of 10 union values
- If there is a value in A OR B, the value will be stored somewhere in EC
- We need to check vice-versa: if there is a value in EC, then it must also appear in EA OR EB
- We need this constraint for the solver to work correctly
We can then use a switch array or a marker to indicate which if the indices are unused (when not all the values in either A or B are used).
