what is constraint programming?

solving problems that can be expressed as a number of constraints over some variables

• some problems that can be expressed this way (today)
• definition of constraints (today)
• how to solve such problems (other lessons)

why?

some problems can be formulated as:

1. some variables
2. some constraints on them

each constraint restrict the values of some variables

which problems?

only those of the kind:

find some values for some variables so that some constraints are satisfied

example: eight queens

place eight queens in a chessboard so that they cannot take each other

how to encode as variables and constraints:

variables

two for each queen: x1,y1, x2,y2, …

constraints

• no two queens on the same row: x1 ≠ x2, x1 ≠ x3, …
• no two queens on the same column: y1 ≠ y2, y1 ≠ y3, …
• no two quenns on the same diagonal: |x1-x2| ≠ |y1-y2|, …

not the only way to formulate the problem!

another formulation

same problem (eight queens)

variables

each queen on its column: variables only for rows: r1,...,r8

constraints

• columns are different by construction
• different rows: r1 ≠ r2, r1 ≠ r3, …
• diagonals: |r1-r2| ≠ 1, |r1-r3| ≠ 2, …

example: 3SAT

given: propositional formula in 3CNF
find: truth assignment satisfying it

each clause ⇒ a constraint

clause: x₁ ∨ ¬x₄ ∨ x₅
constraint: all Boolean values but 010

example: map coloring

color the areas of a map (e.g., nations)
no touching areas of the same color

variables: color for each area
constraints: available colors
constraints: no same color for touching areas

others...

find a schedule (e.g., allocation of time slots for lessons)

find a plan (sequence of action to reach a goal)
(only with some restrictions)

…

constraint satisfaction problem

often: on finite domains

theory: triple ⟨X,D,C⟩

• X set of variables
• D a domain for each variable
• C set of constraints

variables and domains

X = {x₁,…,x_n}
D = {D₁,…,D_n}

each x_i is a variable

each D_i is a set
contains: all possible values for x_i

sometimes: same domain for all variables

constraint

each constraint:

• list of variables
• tuples of allowed values for the variables

example: C₃ = ⟨⟨x₂,x₄⟩, {⟨2,3⟩, ⟨4,6⟩, ⟨1,5⟩}⟩

variables:

x₂ and x₄

values:

• ⟨2,3⟩ means: x₂ = 2 and x₄ = 3 is allowed
• ⟨4,6⟩ means: x₂ = 4 and x₄ = 6 is allowed
• ⟨1,5⟩ means: x₂ = 1 and x₄ = 5 is allowed

all other values are disallowed

a contraint tells: these variables can only take these values

tabular representation of a constraint

C₃ = ⟨⟨x₂,x₄⟩, {⟨2,3⟩, ⟨4,6⟩, ⟨1,5⟩}⟩

in tabular form:

table header: which variables
table rows: which values these variables can take

example

color this graph with two colors only:

• variables: the color of each node
  four nodes, four variables: a,b,c,d
• domains: black and white
• constraints: no same color for adjacent nodes

  a b white black black white

  a c white black black white

  b c white black black white

  c d white black black white

exercise

formulate the “two queens” problem on a 3x3 chessboard

solution

both coordinates for each queen
other formulation do not work (no queen may be in column 1, etc.)

two variables for each queen: x₁,y₁ e x₂,y₂

same domain for all: {1,2,3}

constraints:

first constraint: not the same row

second constraint: not the same column

third constraint: not same diagonal
note: 1112 satisfies this constraint but not the first

exercise

express this propositional formula as variables, values and constraints

{x₁ ∨ ¬x₂, ¬x₂ ∨ ¬x₃, x₃}

solution

variables

one for each Boolean variables

domains

same for all variables: {0,1}

constraints

each clause = a constraint
variables of the constraint = variables of the clause
rows of the constraint = values allowed by the clause
(next slide)

solution: constraints

names

domain of the variable x₁:

the set D_i of the values it can take

scope of a constraint:

its variables (the header of the table)

relation of a constraint

the set of its tuples of values (the rows of the table)

same constraint?

trivia: may a problem have the same constraint on variables x₁,x₂ and on variables x₃,x₄?

same constraint? no

constraint = list of variables and allowed values

two constraints may have the same relation (allowed values) on different variables

• C₁=⟨⟨x₁,x₂⟩,R⟩
• C₂=⟨⟨x₃,x₄⟩,R⟩

still, two different constraint (different variables)

same relation, not same constraint

common relations

the relation of a constraint can be expressed as:

• a set of tuples (rows of values)
• a “known” relation

second is easier; but requires the relation to be predefined in the solver;
example: the relation “all-different” is often available

in the theory of CSP, usually only the first

unary constraints

a constraint on a single variable

restricts the possible values of its variable

common changes involving unary constraints:

• universal domain: D_t = D₁ ∪ … ∪ D_n;
  all variables have domain D_t;
  unary constraints to restrict each x_i to D_i
• opposite: remove from D_i all values not satisfying the unary contraints for each x_i

one can assume that the domain is the same for all variables
OR
one can assume that no constraint is unary

not both!

node consistency

a variable is node-consistent if every value of its domain satisfies all unary constraintson that variable

a CSP is node consistent if all its variables are

ensuring node consistency

remove values not satisfying a unary constraints from the domain

D_i' = D_i ∩ { v | ∀ C=⟨x_i,R⟩   ⟨v⟩ ∈ R }

a value v is kept only if it in the relation of every unary constraint fot the variable

same as removing all values not satisfying one or more constraints:

D_i' = D_i \ { v | ∃ C=⟨x_i,R)   ⟨v⟩ ∉ R }

this transformation makes all unary constraints unnecessary
(always satisfied)

constraint propagation

ensuring a problem is consistent is a way to simplify the problem without changing its solutions

is a form of constraint propagation:
from ⟨v⟩ ∉ R to the removal of v to the domain

exploit the effects of some constraints

other propagations of constraints are possible

solutions

solution = assignment from variables to values
all constraint satisfied

function f : V → ∪ D
from variables to elements of the domains

• f(x_i) ∈ D_i
• for each constraint C=(⟨x₁,...,x_n⟩,R), it holds ⟨f(x₁),…,f(x_n)⟩ ∈ R

equivalence

equivalent problems = same solutions

example: constraint propagation
changes the problem without changing the solution
new problem is equivalent to the old

other such transformations exist

normalization

more constraints may have the same variables

can be merged in a single constraint
only tuples in both

formally: if the constraint with scope S are C₁ = ⟨S,R₁⟩, C₂ = ⟨S,R₂⟩ … C_m = ⟨S,R_m⟩ their combination is:

C_c = ⟨S, R₁ ∩ R₂ ∩ … ∩ R_m⟩

this single constraint is equivalent to the original ones

normal form

merge all constraints with the same scope

• common assumption in theoretical studies
• implemented systems do not require it

composition

new constraint, consequence of others

two binary constraints with a shared variable:

⟨⟨x₁,x₂⟩,R₁⟩
⟨⟨x₂,x₃>,R₂⟩

composition:

⟨⟨x₁,x₃⟩,R₃⟩
where ⟨a,b⟩ ∈ R₃ ↔ ∃ c . ⟨a,c⟩ ∈ R₁ and ⟨c,b⟩ ∈ R₂

combine constraints, remove the shared variable

generalize to an arbitrary number of constraints
possibly not binary
arbitrary set of variables in the composition

solving

how to find a solution:

• inference: find new constraints from old ones;
  may make the problem easy to solve
• search: look for a solution, for example:
  • backtracking and variants
  • local search

the two appoaches, combined

the two appoaches can be combined

example: generate new constraint by inference, then use backtracking

backtracking may work better with more constraints

backtracking

• choose a variable x
• sort the values of its domain in some way
• for each value v, add the constraint x=v;
  recursively search for a solution

partial consistency

partical assigment: only some variables have a value;
example: x₁ = 1, x₂ = unassigned, x₃ = 5

some constraints may already be violated;
example: a constraint on x₁ and x₃ that does not have the tuple ⟨1,5⟩

allows for backtracking before choosing a value for x₂

backtracking variants

backmarking

avoid some checks of consistency

look-ahead

check in advance what happens with a value for a variable

backjumping

skip recursive calls if they are the same as others already done

constraint learning

store information discovered during search as new constraints

other topics

• local consistency and constraint propagation
• hybrid algoriths
• optimization
• constraint logic programming
• complexity
• dual problem and decomposition

binary problems

common restriction: only constraints with two variables

same as: at most two variables each constraint,
since unary constraints can be removed

cam be visualized as graphs:

• each variable is a node
• each constraint is an edge between its two variables

example

C₁ = ⟨<x₁,x₂>,R₁⟩
C₂ = ⟨<x₂,x₃>,R₂⟩
C₃ = ⟨<x₃,x₁>,R₂⟩
C₄ = ⟨<x₁,x₄>,R₂⟩

• often, the name of constraints are omitted in the graph
• the graph depends only on the scopes of constraints, not on their relations

the graph is therefore not a representation of the problem
only one aspect of its (the way the variables are linked)

primal graph

also non-binary problems

• a node for each variable
• an edge between two nodes if the variables are both in some scope

notes:

• edges are never labeled
• problems with different scopes may correspond to the same graph;

  example: problems with a single constraint, with scope ⟨x₁,x₂,x₃⟩,
  problem with three constraints, with scopes ⟨x₁,x₂⟩, ⟨x₂,x₃⟩, and ⟨x₃,x₁⟩
  same primal graph:

hyphergraph

alternative representation for non-binary problems

hyphergraph = nodes + sets of nodes (hypheredges)
graph: special case where all hypheredges are sets of two nodes

hyphergraph for the constraint with scope ⟨x₁,x₂,x₃⟩:

hyphergraph for the constraints with scope ⟨x₁,x₂⟩, ⟨x₂,x₃⟩, and ⟨x₃,x₁⟩:

exercise

write a program that generates the constraints for a Sudoku puzzle

other kind of constraints

• linear constraints, like x + 2y - z > 2
• equality and non equality between tree-like structures

problems of the first kind are solved by elimination algorithms or the symplex method

problems of the second kind are solved by an extended unification algorithm