L03: Sequences Flashcards
Explain this Essence’ Model:
language ESSENCE’ 1.0
given n : int
find x: matrix indexed by [int(0..n)] of int(0..n)
such that gcc(x, [i | i : int(0..n)], x)
This is the Essence’ model for the Magic Sequence
- Given an integer n
- Find a sequence of integers indexed from 0-n, each with a domain of 0-n
- Such that the number of occurrences of i (from all values of i from 0-n) in the sequence x is x[i]
How can we build a constraint model for unbounded sequences?
We can solve a series of CSPs, incrementally increasing the length of the sequence (if not 1, then 2, then 3, and so on).
This way, we can find the solution with the shortest sequence.
In the worst-case scenario this is an infinite process.
How do we know which viewpoint to use?
It depends on the constraints of the problem
For example, if the values must be adjacent (consecutive indexes), then the second viewpoint is easier to visualise the solution
For example, if the first 3 variables of the sequence must form an English word, then we just need a table constraint one the first 3 variables, in which case the first viewpoint is easier to understand.
What are some types of sequences?
- Fixed-length sequence
- Bounded-length sequence
- Unbounded sequence
What are the 5 stages of constraint modelling?
Ill-defined problem statement
-> Well-defined problem defined statement
-> Abstract constraint model
-> Solver-independent constraint model
-> Solver-specific constraint model
What does constraint modelling do?
Constraint modelling maps a well-defined problem statement to a solver-independent constraint model.
What does Savile Row do?
Savile Row maps a solver-independent constraint model to a solver-specific constraint model.
What does the global cardinality constraint (gcc) do?
gcc(X, Vals, C)
For each non-decisions expression Vals[i], the number of occurrences of Vals[i] in X equals C[i]
What is a permutation?
A permutation of a sequence is the ordering of elements in the sequence.
When finding the permutation of a sequence, the elements of the sequence is known but their correct arrangement is not.
What is a sequence?
- A sequence is an ordered list of elements
- Ordered in the sense that a sequence has a first element, second element, etc.
- Repetition is allowed
What is a viewpoint?
A viewpoint is a choice of variables and domains sufficient to characterise the problem
I.e. from a certain assignment of variables, we can derive a solution
What is an Abstract Constraint Model?
When there are patterns in the problems we want to solve, we can write our abstract constraint model in terms of these patterns.
However these are typically not supported by constraint solvers and so they need to be modelled as constrained collections of more primitive objects.
We can develop corresponding modelling patterns for representing and constraining these combinatorial objects and reduce the effort when modelling a new problem.
When viewed abstractly, many combinatorial problems that we wish to tackle with constraint solving exhibit common features.
Abstractly: above the level at which constraint modelling decisions are made.
What is an equivalence class and how are they created and avoided?
An equivalence class is a set of assignments that have the same value or will be interpreted the same.
Equivalence classes can be created when dummy values are used.
We can avoid equivalence classes by placing constraints on the dummy variables, for example if we are using 0 as the dummy variable (therefore is not in the domain), then all 0s must appear at the end of the sequence.
What is the first viewpoint of permutations?
Assume all the elements of the permutation are distinct
First viewpoint is as fixed-length
Sequence is indexed 1-n, and the domain is represented as alphabetical letters
E.g. if the index is 1-6, then the domain for each decision variable is a-f
We are assigning a value to each index
What is the problem with infinite domains in constraint modelling?
With infinite domains in the abstract specification, it will not be possible to map the abstract constraint specification down to a finite-domain CSP.
