L02: Modelling Introduction Flashcards
What are some common features of constraint languages? (5)
- Allow us to declare decision variables, and their domains
- Often support arrays of variables
Remember the order and colour grids from the Steel Mill example
And iteration over these arrays for concision - Allow us to model problem classes.
- All support extensional/table constraints (those are the basic building blocks)
- Operators allow us to build constraint expressions that are represented intensionally
Arithmetic: +, -, x, *, absolute value
Logical: AND, OR, NOT
What are some examples of constraint models?
- Steel Mill Slab Design
- Crystal Maze
- Sudoku
What are the 2 components of constraint solving?
- Systematic search
- Constraint propagation
What are the 4 components used to structure a constraint model?
- Given parameters
- Find decision variables
- Such That constraints
- Min/Maximising objective (for COP)
What can we use instead of table/extensional representation?
Intensional representation
What could the objectives of a COP be?
- Minimising waste or cost.
- Minimising time taken (e.g. for scheduling).
- Maximising profit.
What does a constraint model do?
- A constraint model maps the features of a combinatorial problem onto the features of a constraint satisfaction problem (CSP).
- A constraint model is a recipe that produces a CSP/COP
What is a constraint language?
- A constraint language is a language used to specify constraints for a model
- I.e. constraint programs are written in constraint languages
What is a problem class?
A problem class describes a family of problems, related by a common set of parameters. A problem class is specified by one or more parameters.
- Obtain an instance: give values for the parameters.
- Example: n-queens problem class.
Place n queens on an n x n chess board such that no pair of queens attack each other. - Another example is the sudoku problem class
What is a problem instance?
- An instance is specified from a class by instantiating the parameters to particular values.
- An individual CSP/COP represents a problem instance.
- Constraint solvers solve individual instances.
What is intensional representation?
Constraint solvers provide a library of commonly-occurring constraints that can be specified much more concisely
Internally, the solver usually represents these constraints Intensionally:
- An expression that can be evaluated:
E.g. =, <, ≤, ≠. - An algorithm that can be executed:
AllDifferent, various kinds of counting constraints
What is the (finite-domain) constraint satisfaction problem (CSP)?
Given:
- A finite set of decision variables.
- For each decision variable, a finite domain
of potential values. - A finite set of constraints on the decision
variables.
Find:
An assignment of values to variables such that
all constraints are satisfied.
What is the advantage of having a table constraint?
We can represent any constraint we wish to model like this
What is the advantage of using intensional representation?
Simple to check whether an assignment satisfies this constraint as there is no need to check through the whole table, one comparison/algorithm can be applied
What is the Constrained Optimisation Problem (COP)?
Given:
- A CSP + an objective function.
- E.g. maximise/minimise value of some variable/expression.
Find:
- An assignment of values to variables such that:
All constraints are satisfied.
The objective is optimised.
