Constraint Programming

• CSP = Constraint Satisfaction Problem
• COP = Constraint Optimization Problem
• It. Problema di Soddisfacimento/Ottimizzazione di/con Vincoli

A declarative approach

• Model & then solve (a bit like MIP)
• Model = variables + constraints
• Rich set of constraints (much more than linear in-equalities)

A Practical Application

• Netherlands railways: 5,500 trains per day
• In 2009: timetable complete redesign (OR and CP)
• Less delay, more trains, profit increase: ~\$75M

Another Practical Application

• Port of Singapore: > 200 shipping lines, > 600 connected ports
• Problem: yard location assignment, loading plans
• For years, the Yard planning system (CP based) assisted the job

A third Practical Application

• Rosetta-Philae mission
• In 2014, first (partially successful) probe landing on a Comet
• Probe-spacecraft communication pre-scheduled via CP

CP - Quick Facts

A few reasons for using CP:

• Rich modeling language
• Fast prototyping
• Easy to maintain (modifications are simple)
• Extensible (new constraints, customizable search...)
• Very good framework for hybrid approaches

Overall:

• It's a good solution technique!
• Especially for messy, real-world, problems

Step by step

Map Coloring

4 available colors, different colors for contiguous regions

Map Coloring

4 available colors, different colors for contiguous regions

• Pick and color a region
• Pick another region, choose a compatible color
• Rinse & repeat

Map Coloring

4 available colors, different colors for contiguous regions

Partial Latin Square

• Think of that as "Poor's man sudoku"
• Different numbers (1 to 4) on rows and columns

Partial Latin Square

• Think of that as "Poor's man sudoku"
• Different numbers (1 to 4) on rows and columns

• Pick a cell, insert compatible value
• Rinse & repeat

Partial Latin Square

• Think of that as "Poor's man sudoku"
• Different numbers (1 to 4) on rows and columns

Partial Latin Square

• Think of that as "Poor's man sudoku"
• Different numbers on rows and columns

• Clear one of more moves
• Restart to insert numbers

Partial Latin Square

• Think of that as "Poor's man sudoku"
• Different numbers on rows and columns

CP in a Nutshell

You see? There is a pattern.

• We reason on the constraints to narrow down the possible choice
• We make (and unmake) some choices

The core ideas in Constraint Programming are the same!

To the point that for many people:

CP in a Nutshell

You see? There is a pattern.

• We reason on the constraints to narrow down the possible choice
• We make (and unmake) some choices

The core ideas in Constraint Programming are the same!

But I am not many people! I think this formula is much better:

• CP is a declarative approach, remember?
• So it all starts with a declarative model

In the next slides we will focus on each of the three aspects

Constraint Systems

CP = model + ...

Constraint Satisfaction Problem

• First, we need to define the kind of problem we are interested in:

where:

• $X$ is a set of variables
  • $x_i$ is a single variable
  • In principle: any kind of variable!
• $D$ is a set of domains
  • $x_i$takes values in $D(x_i)$
• $C$ is a set of constraints

More on Constraints

Constraint scope (Italian: ambito)

• A constraint $c_j$ is defined over a subset of $X(c_j)$ of the variables
• $X(c_j) \subseteq X$ is called the scope of the constraint

Tuple

• A tuple $\tau$ or arity $n$ is just a sequence of $n$ values

Relation

• Let $S$ be a sequence of sets $S_0, S_1, ...$
• A relation $R$ over $S$ is a subset of the Cartesian product. I.e.:

$$R \subseteq S_0 \times S_1 \times ...$$

More on Constraints

Constraint

• A constraint $c_j$ is a relation over the domains of $X(c_j)$. I.e.:

$$c_j \subseteq \prod_{x_i \in X(c_j)} D_i$$

Here's the main idea:

• A tuple in the Cartesian product = an assignment of the variables
• A constraint is just a list of feasible assignments

A bit abstract, so let's make an example

An example CSP (definition-like)

Variables: $X = \{x_0, x_1\}$

Domains: $D(x_0) = \{0..2\}$, $D(x_1) = \{0..2\}$

Constraints:

$$\begin{align} c_0 &= \left(\begin{aligned} (0, 0)\\ (0, 1)\\ (0, 2)\\ (1, 1)\\ (1, 2)\\ (2, 2) \end{aligned}\right) & c_1 &= \left(\begin{aligned} (0, 0)\\ (0, 1)\\ (0, 2)\\ (1, 0)\\ (1, 1)\\ (2, 0) \end{aligned}\right) \end{align}$$

Solution of a CSP

Formally:

$$\tau \in \prod_{x_i \in X} D(x_i) \ : \ \tau[X(c_j)] \in c_j, \forall c_j \in C$$

where:

• $\tau[X(c_j)]$ is the projection of $\tau$ over $X(c_j)$
• $\tau[X(c_j)]$ = sequence of values assigned by $\tau$ to variables in $X(c_j)$

Solution of a CSP

Formally:

$$\tau \in \prod_{x_i \in X} D(x_i) \ : \ \tau[X(c_j)] \in c_j, \forall c_j \in C$$

The solutions in our example: $(0, 0)$, $(0, 1)$, $(0, 2)$, $(1, 1)$

Down to Earth

Any kind of domain?

Down to Earth

Any kind of domain?

In practice:

• Integer variables
• Real variables
• Set variables! (e.g. $x_i \in \{ \{0, 1\}, \{0\} \}$)
• Graph variables!
• ...

In this course:

• Strong emphasis on finite, integer domains
• The most studied case

Down to Earth

Any kind of constraints?

Down to Earth

Any kind of constraints?

• With finite domain variables, yes!
• We can actually list all the feasible assignments

This is called extensional representation

• Very general
• Possibly inconvenient and inefficient (large domains)

We may prefer a symbolic or intensional representation:

• More compact, more clear, less general

Constraint Libraries

Intensional forms are made possible by Constraint libraries

• Constraint library = collection of constraint types

Our first constraint library:

Equality:

• Notation: $x = y$
• Semantic: satisfied if $x$ is equal to $y$

Disequality:

• Notation: $x \neq y$
• Semantic: satisfied if $x$ is not equal to $y$

Map Coloring as a CSP

Variables and domains:

• $x_i \in \{0..3\}$, for each region

Constraints:

• $x_i \neq x_j$ if region $i$ and $j$ are contiguous

Partial Latin Square as a CSP

Variables and domains:

• $x_{i,j} \in \{1..4\}$, for each cell $i, j$
• $i \in \{0..3\}$ = row index, $j \in \{0..3\}$ = column index

Constraints:

• $x_{i,j} \neq x_{i,h} \quad \forall i, \forall j < h$
• $x_{i,j} \neq x_{h,j} \quad \forall j, \forall i < h$

Partial Latin Square as a CSP

Variables and domains:

• $x_{i,j} \in \{1..4\}$, for each cell $i, j$
• $i \in \{0..3\}$ = row index, $j \in \{0..3\}$ = column index

Constraints:

• $x_{i,j} = v$ is cell $i, j$ is pre-filled with value $v$

Constraint Systems

CP = model + constraint reasoning + ...

One Missing Piece

• We would never put a 3 there (not compatible)
• Can we formalize this deduction?

Filtering

• $x_{3,1} \neq x_{3,2} \Rightarrow x_{3,2} \neq 4$
• $x_{2,2} \neq x_{3,2} \Rightarrow x_{3,2} \neq 3$
• $x_{0,2} \neq x_{3,2} \Rightarrow x_{3,2} \neq 2$

Filtering

• The only possible value for $x_{3,2}$ is 1

Filtering

• Alternative terms: pruning, propagation
• My convention:
  • Pruning = the act of removing a single value
  • Filtering = the process that guides pruning
  • Propagation = later!
• Italian: propagation = propagazione

Filtering

• For constraints in extensional form:
  • General methods (we will see them later)
• For constraints in intensional form:
  • Specialized filtering algorithms
  • Those are specified in the constraint library
  • Alternative names: filtering rules, propagators

Filtering for our First Constraint Library

Equality constraint: $x = y$

• Rule 1: $v \in D(y) \wedge v \notin D(x) \longrightarrow v \notin D(y)$
• Rule 2: $v \in D(x) \wedge v \notin D(y) \longrightarrow v \notin D(x)$

Examples:

• Before filtering: $x \in \{0,1\}, y \in \{1,2\}$
• After filtering: $x \in \{1\}, y \in \{1\}$

Filtering for our First Constraint Library

Disequality constraint: $x \neq y$

• Rule 1: $D(x) = \{v\} \longrightarrow v \notin D(y)$
• Rule 2: $D(y) = \{v\} \longrightarrow v \notin D(x)$

Examples:

• Before filtering: $x \in \{1\}, y \in \{1,2\}$
• After filtering: $x \in \{1\}, y \in \{2\}$

An Example on the PLS

• All original domains are $\{1..4\}$
• Let's filter all the constraints in order
• By row and then column

An Example on the PLS

• Constraint $x_{0,0} \neq x_{0,2}$ prunes 2 from $D(x_{0,0})$

An Example on the PLS

• Constraint $x_{0,1} \neq x_{0,2}$ prunes 2 from $D(x_{0,1})$

An Example on the PLS

• Constraints $x_{0,2} \neq x_{0,j}$ and $x_{0,2} \neq x_{i,2}$ prune a lot

An Example on the PLS

• By filtering all constraints in order, we get this

An Example on the PLS

• Yep: $D(x_{3,2})$ and $D(x_{3,3})$ are now singletons
• Hence, our filtering rules for the $\neq$ constraints can be triggered
• If we do, we can filter more

Propagation

• Propagation is controlled by a propagation algorithm

Our First Propagation Algorithm

Algorithm: AC1

• dirty = true
• while dirty:
  • dirty = false
  • for $c_j \in C$:
  • $D' = \mathit{filter}_{c_j}(D)$
  • if $D' \neq D$: dirty = true

Where $\mathit{filter}_{c_j}(D)$ is a procedure that:

• Given the current variable domains...
• ...Applies the filtering algorithm of $c_j$...
• ...And then returns the updated domains

Fix Point Theorem

Proof: We will prove the result in two steps:

• First, we show that AC1 always terminates...
• ...When no more pruning can be done
• Second, we show that the processing order does not matter

The proof relies on some properties of $\mathit{filter}_{c}(D)$

Fix Point Theorem

The function filter($c$) is inflationary, i.e.:

• True because a filtering algorithm can only remove domains values
• Caveat:
  • Technically, $\mathit{filter}_{c}(D)$ is inflationary w.r.t. the order $\supseteq$
  • Hence, the term may sound a bit misleading

Consequence: AC1 always terminates

• In the worst case, when $D$ becomes empty

Fix Point Theorem

The function $\mathit{filter}_c(D)$ is monotone, i.e.:

• True because removing a value from $D_i \in D$:
  • can only reduce the number of feasible assignments
  • and hence increase the number of values that can be pruned

Consequence: the processing order of $c_j$ does not matter

• Whenever a filtering algorithms prunes something...
• ...the other algorithms just become stronger

Fix Point Theorem

Fix Point Theorem

Thanks to the fix point theorem:

• We can focus on filtering
• and let the propagation algorithm handle the rest

Fix Point Theorem

Warning: the constraint processing order

• does not affect the fix point
• does affect the number of AC1 iterations

Some orders may be more efficient

• Interesting (and challenging) research question
• NP-hard in general

AC1 on the PLS

• If we apply AC1 to our PLS

AC1 on the PLS

• If we apply AC1 to our PLS
• We get this (we pruned a lot!)...
• ...and still we don't have a solution :-(

Constraint Systems

CP = model + constraint reasoning + search

Complexity of a CSP

In general, filtering and propagation are not enough to solve a CSP

• In fact solving a CSP is NP-hard
• No surprise, since the definition is so general...

Don't forget that:

(Basic) Search in CP

The simplest search approach in CP is Depth First Search:

• function $DFS(CSP)$:
• if a solution has been found: return true
• if the CSP is infeasible: return false
• for $d$ in $\mathit{decisions}(CSP)$:
• if $DFS(apply(d, CSP))$: return true
• return false

(Basic) Search in CP

The simplest search approach in CP is Depth First Search:

• If the problem is infeasible: return false
• If a solution has been found: return true
• Otherwise, build a set of "decisions":
  • Try to apply a decision
  • If successful return true
  • Othewise, backtrack
    • Un-make the last decision
    • Try with the next one
• If no decision is successful, return false (the problem is infeasible)

(Basic) Search in CP

The simplest search approach in CP is Depth First Search:

• function $DFS(CSP)$:
• if a solution has been found: return true
• if the CSP is infeasible: return false
• for $d$ in $\mathit{decisions}(CSP)$:
• if $DFS(apply(d, CSP))$: return true
• return false

In our pseudo-code, backtracks are handled via recursion.

• In practice, this may be quite inefficient...
• ...We'll discuss this point again much later in the course

(Basic) Search in CP

The simplest search approach in CP is Depth First Search:

• function $DFS(CSP)$:
• if a solution has been found: return true
• if the CSP is infeasible: return false
• for $d$ in $\mathit{decisions}(CSP)$:
• if $DFS(apply(d, CSP))$: return true
• return false

Unclear points:

• How to detect if a problem is infeasible?
• What are the decisions returned by $\mathit{decisions}(CSP)$?
• What does it mean to "apply a decision"?

DFS in CP

A problem is infeasible if we have a domain wipeout

• Domain wipeout = empty domain, because of propagation
• This is a sufficient condition
• This is not a necessary condition
  • I.e. if there is wipeout, then the problem is infeasible
  • But infeasibility may hold even if there is not wipeout
  • More on this later!

DFS in CP

They are constraints! For example:

• We pick the first unbound variable $x_i$
  • Unbound variable = variable with non-singleton domain
• We pick the smallest value $v$ in $D(x_i)$
• Our decisions are $x_i = v\ $ and $x_i \neq v$

There are many more options, but for now let us stick to this.

DFS in CP

It means:

• Adding (posting) the constraint to the problem
• Triggering its filtering algorithm for the first time

Remember: on backtrack, the constraint must be removed.

DFS on our PLS

• First unbound variable = $x_{0,0}$
• Minimum value = 1
• We post $x_{0,0} = 1$, and the propagate

DFS on our PLS

• First unbound variable = $x_{0,0}$
• Minimum value = 1
• We post $x_{0,0} = 1$, and the propagate

DFS on our PLS

• With just one search decision!
• This result is enabled by the use of constraint reasoning

Constraint Systems

A Modeling Excercise

Il Cartello delle Chincaglierie

Giani, Piero, Marisa e Luisanna, sono quattro (stagionati) abitanti di un piccolo paesello del centro Italia. I quattro sono legati da distanti (ma indiscutibili) legami di parentela e pertanto, come vuole il buon costume, di tanto in tanto per le occasioni si scambiano regali. I quattro non è che vadano proprio d’amore e d’accordo e così, un po’ per scherzo ed un po’ per dispetto, da qualche anno continuano a regalarsi le stesse chincaglierie

Nella fattispecie, le chincaglierie sono: una riproduzione in vetro di una conchiglia tropicale, una vecchia clessidra, una lampada in fibre ottiche (di quelle pelose) ed una statuetta a forma di cavalluccio marino.

Il Cartello delle Chincaglierie

Siamo al terzo anno in cui le cianfrusaglie devono essere scambiate e finora non ci sono stati “incidenti diplomatici”. All’indomani dell’inizio del quarto anno, Gianni deve ancora fare il suo regalo, torturato dal timore essere il primo a scatenare uno scandalo. Il poveretto ripensa con preoccupazione agli scambi a cui ha partecipato:

• Il primo anno, Gianni aveva in casa la conghiglia, che ha regalato a Marisa. Lo stesso anno, Marisa ha regalato a Gianni la lampada.
• Il secondo anno, Gianni ha regalato la lampada a Piero ed ha ricevuto in dono da Luisanna la clessidra.

Il Cartello delle Chincaglierie

Fortunatamente, Gianni è venuto a conoscenza tramite suo nipote di una nuova metodologia che si chiama Programmazione a Vincoli, che pare possa aiutarlo a risolvere i suoi problemi...

Si modelli il problema dello scambio dei regali tramite Programmazione a Vincoli e si indichi a quale persona Gianni potrà regalare la clessidra senza scatenare una bagarre.

Il Cartello delle Chincaglierie (Soluzione)

Si tratta di un Partial Latin Square problem un po’ “camuffato”. Una possibile soluzione consiste nell’introdurre una variabile per ogni persona e per ogni anno (incluso il quarto!):

• $x_{G,0},x_{G,1},x_{G,2},x_{G,3} \in \{conc, cless, lamp, stat\}$
• $x_{P,0},x_{P,1},x_{P,2},x_{P,3} \in \{conc, cless, lamp, stat\}$
• $x_{M,0},x_{M,1},x_{M,2},x_{M,3} \in \{conc, cless, lamp, stat\}$
• $x_{L,0},x_{L,1},x_{L,2},x_{L,3} \in \{conc, cless, lamp, stat\}$

Il Cartello delle Chincaglierie (Soluzione)

Ogni anno, ogni persona possiede esattamente un oggetto:

• $X_{p,i} \neq X_{q,i}, \quad p, q = \{G,P,M,L\}, i \in \{0..3\}$

Nessuno può possedere lo stesso oggetto due volte:

• $X_{p,i} \neq X_{p,j}, \quad p = \{G,P,M,L\}, i,j \in \{0..3\}$

Alcuni scambi sono noti:

• $x_{G,0} = conc$
• $x_{M,0} = lamp, x_{M,1} = conc, x_{G,1} = lamp$
• $x_{L,1} = cless, x_{P,2} = lamp, x_{G,2} = cless$

Il Cartello delle Chincaglierie (Soluzione)

Esiste una sola soluzione feasible:

  Gianni: conchiglia lampada    clessidra  statuetta   
   Piero: clessidra  statuetta  lampada    conchiglia  
  Marisa: lampada    conchiglia statuetta  clessidra   
Luisanna: statuetta  clessidra  conchiglia lampada

Pertanto, Gianni deve regalare la clessidra a Marisa se vuole evitare lo scandalo