L01: Introduction

Question 1

How do we solve problems with constraints?

Answer 1

1. Describe the problem to be solved as a constraint model, a format suitable for input to a constraint solver.
2. Search (automatically) for solutions to the model with a constraint solver.

Question 2

What are the stages of constraint modelling and solving?

Answer 2

1. Constraint modelling
2. Map input problem to CSP
3. Constraint solving
4. Map solution of CSP to input problem

A constraint model maps the features of a given problem onto the features of a constraint satisfaction problem.

The CSP is input to a constraint solver, which produces a solution (or solutions).

Question 3

What is a constraint?

Answer 3

Of the possible combinations of assignments to the
variables in its scope, a constraint specifies:
- Which are allowed
Assignments that satisfy the constraint.

• Which are disallowed
  Assignments that violate the constraint
• I.e. can think of a constraint as a relation.

E.g. if variables tA, tB, represent time for lectures A, B, both taken by student S:
tA ≠ tB

Question 4

What is a decision variable?

Answer 4

A decision variable corresponds to a choice that
must be made in solving a problem.

In simple words, something that decide the value of, e.g. the cell of a sudoku grid

Question 5

What is a domain?

Answer 5

Values in the domain of a decision variable correspond to the options for a particular choice.

A decision variable is assigned a single value from its domain.

Question 6

What is a scope?

Answer 6

A scope is the subset of the decision variables a constraint involves.

Question 7

What is a systematic search?

Answer 7

Systematic Search through a space of partial assignments.
- Extend an assignment to a subset of the variables
incrementally.
- Backtrack if establish that current partial assignment
cannot be extended to a solution.

Question 8

What is constraint programming?

Answer 8

An active field of Artificial Intelligence in which we study how to model and solve constraint satisfaction problems.

Question 9

What is constraint propagation?

Answer 9

• Deduction based on constraints, current domains.
• Usually recorded as reductions in domains.

Question 10

What is the constraint satisfaction problem?

Answer 10

A general way in which we can represent and
solve decision-making problems:
Given:
1. A set of decision variables.
2. For each decision variable, a domain of potential
values.
3. A set of constraints on the decision variables.

Find:

An assignment of values to variables such that all
constraints are satisfied.