The n-queens Problem

• Place $n$ queens on a $n\times n$ board
• No two queens should be able to attack

The n-queens Problem

Modeling the n-queens Problem

Suggestion (important):

To design a model, always start from the variables

• Q1: what are the problem decisions?
• Q2: how should we encode such decisions?

Modeling the n-queens Problem

Suggestion (important):

To design a model, always start from the variables

• Q1: what are the problem decisions?
• Q2: how should we encode such decisions?

Variables, first hypothesis:

• $x_{i,j} \in \{0, 1\}, \quad \forall i,j = 0..n-1$
• $x_{i,j} = 1$ iff there is a queen in position $i,j$

Variables, second hypothesis:

• $x_{j} \in \{0..n-1\}, \quad \forall j=0..n-1$
• $x_{j} = i$ iff the queen on column $j$ is on row $i$

Modeling the n-queens Problem

Suggestion:

• At this point, try to encode the constraints
• It may be much easier for some variable choices

Modeling the n-queens Problem

Suggestion:

• At this point, try to encode the constraints
• It may be much easier for some variable choices

Constraint: "No two queens on the same column"

• HP1: ???
• HP2: trivial! There is already a variable per column

Constraint: "No two queens on the same row"

• HP1: ???
• HP2: $x_i \neq x_j, \quad \forall i < j$

Modeling the n-queens Problem

Suggestion:

• At this point, try to encode the constraints
• It may be much easier for some variable choices

Constraint: "No two queens on the same lo-left/up-right diagonal"

• HP1: ???
• HP2: ???

Modeling the n-queens Problem

• Same lo-left/up-right diagonal...

Modeling the n-queens Problem

• Same lo-left/up-right diagonal = those distances are identical

Modeling the n-queens Problem

• And the reverse relation holds for the up-left/lo-right diagonal

Arithmetic in CP

Arithmetic in CP

A first alternative:

But what about similar cases?

Arithmetic in CP

A first alternative:

But what about similar cases?

• More constraints?
  • $x + y \neq v$
  • $x - y = v$
  • $x + y = v$
  • ...

• This is very inconvenient...

Arithmetic Constraints

A second alternative:

• From:
  • $x + y \neq v$
• To:
  • $z = x + y$
  • $z \neq v$

This is much more versatile!

Arithmetic Constraints

Thanks to this approach:

• We can encode complex expressions
• Using a limited number of modeling components

For example:

Arithmetic Constraints

Do we have to post the individual constraints separately?

• In some (low-level) constraint languages, yes
  • Example: FlatZinc
• But most constraint solvers provide automatic expression parsing
  • This is done by constructing an "expression tree"
  • According to the syntax of the operators
  • And their priority rules

Expression Tree

• Nodes = constraints, variables, constants, and expressions
• Typically different implementation for each type

Time to Enrich Our Constraint Library

Let's add some constraints to our library!

• $z = x + y\quad$ sum constraint
• $z = x\,y\quad$ multiplication constraint
• $z = |x|\quad$ absolute value constraint
• $z = \min(x, y)\quad$ minimum constraint

where:

• $z$ is automatically introduced when parsing the expression
• $z$ is either a fresh variable or an expression object
  • Conceptually: expression object = variable (different impl.)
• $x$ and $y$ can be variables, expression objects, or constants

Time to Enrich Our Constraint Library

Constraints:

• $z = x / y\quad$ integer division constraint
• $z = x - y\quad$ difference constraint
• $z = \max(x, y)\quad$ maximum constraint

Time to Enrich Our Constraint Library

Constraints:

• $z = x / y\quad$ integer division constraint
• $z = x - y\quad$ difference constraint
• $z = \max(x, y)\quad$ maximum constraint

Are often available, but can be implemented internally as:

• $y\,z = x\quad$ (typical limitation: $y$ must be positive)
• $z = x + (-y)$
• $z = -\min((-x), (-y))$

Time to Enrich Our Constraint Library

So we have:

• $z = x + y\quad$ sum constraint
• $z = x - y\quad$ difference constraint
• $z = x\,y\quad$ multiplication constraint
• $z = x / y\quad$ integer division constraint
• $z = |x|\quad$ absolute value constraint
• $z = \min(x, y)\quad$ minimum constraint
• $z = \max(x, y)\quad$ maximum constraint

And the filtering algorithms?

• We'll see them later!

Back to the nqueens

We can now model the problem:

• $x_i \in \{0..n-1\}, \quad i = 0..n-1$
• $x_i \neq x_j, \quad \forall i < j$
• $x_j - x_i \neq (j-i), \forall i < j$
• $x_j - x_i \neq -(j-1), \forall i < j$

Back to the nqueens

Constraint Systems

Arc and Bound Consistency

A Systematic Approach to Filtering

• Our constraint library is growing
• Each constraint requires a filtering algorithm

If we want the situation to stay manageable...

We will start from the simplest case, i.e. binary constraints

• In the first lecture we have seen $=$ and $\neq$
• Now we will add a few more: $<$, $\leq$, $>$, and $\geq$

Filtering Examples for Binary Constraints

Equality constraint, $x = y$:

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

Disequality constraint $x \neq y$

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

Inequality constraint $x \leq y$:

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

How to Filter Binary Constraints?

Informally, we remove a value $v$ from domain $D(x)$:

• If it cannot be extended to a feasible assignment for $c_j$...
• ...by using only the values in $D(y)$.

How to Filter Binary Constraints?

Informally, we remove a value $v$ from domain $D(x)$:

• If it cannot be extended to a feasible assignment for $c_j$...
• ...by using only the values in $D(y)$.

Formally, for a binary constraint $c$:

The definition for $w \in D(y)$ is of course analogous.

Arc Consistency

Arc Consistency

• We can prune all and only the values that lack a support.
• Once we are done, we say that Arc Consistency holds for $c$

Formally:

• Why is it called Arc Consistency?
• Because we can view a CSP as a graph

AC and the Constraint Graph

Constraint Graph

Let's see an example on our map-coloring problem:

• The variables correspond to the graph nodes

AC and the Constraint Graph

Constraint Graph

Let's see an example on our map-coloring problem:

• The variables correspond to the graph nodes
• Binary constraints correspond to arcs in the graph

Importance of Arc Consistency

Arc Consistency is important for several reasons:

• It provides a formal characterization of filtering
• It's the best we can achieve by reasoning on a single binary $c$

• This is a very strong property
• Does the guarantee extend to multiple constraints?

Local vs Global Consistency

Let's consider this state of our example PLS:

• All constraints are AC

Local vs Global Consistency

Let's consider this state of our example PLS:

• All constraints are AC
• But if we assign $1$ to $x_{0,1}$...

Local vs Global Consistency

Let's consider this state of our example PLS:

• All constraints are AC
• But if we assign $1$ to $x_{0,1}$ there is no feasible completion

Local vs Global Consistency

• AC provides guarantees only for a single constraint
• For this reason, we say that:

Can we enforce global consistency on a problem?

• Yes, but it is as complex as solving the problem (in general)

And what is the complexity of enforcing AC for single constraints?

Complexity of Enforcing AC

The complexity of a filtering algorithm is very important

• Many executions in each search node...
• ...And DFS explores an exponential number of nodes

Consequence: strong impact on the performance

Let's see the complexity of enforcing AC on our constraints!

Complexity of Enforcing AC

The complexity of a filtering algorithm is very important

• Many executions in each search node...
• ...And DFS explores an exponential number of nodes

Consequence: strong impact on the performance

Let's see the complexity of enforcing AC on our constraints!

Assumptions:

• Lookup $v$ in $D(x)$: complexity $O(1)$
• Iterating over $D(x)$: complexity $O(\left|D(x)\right|)$
• Get size of $\left|D(x)\right|$: complexity $O(1)$
• Prune a value: complexity $O(1)$

Complexity of AC ($=$, $\neq$)

Equality ($x = y$): $v \in D(x), v \notin D(y) \longrightarrow v \notin D(x)$

Complexity of AC ($=$, $\neq$)

Equality ($x = y$): $v \in D(x), v \notin D(y) \longrightarrow v \notin D(x)$

• Iterate over $D(x)$
• For each $v$, check whether $v \in D(y)$ and possibly prune
• Total complexity for $x$ and $y$: $O(|D(x)| + |D(y)|)$

Complexity of AC ($=$, $\neq$)

Equality ($x = y$): $v \in D(x), v \notin D(y) \longrightarrow v \notin D(x)$

• Iterate over $D(x)$
• For each $v$, check whether $v \in D(y)$ and possibly prune
• Total complexity for $x$ and $y$: $O(|D(x)| + |D(y)|)$

Disequality ($x \neq y$): $D(x) = \{v\} \longrightarrow v \notin D(y)$

Complexity of AC ($=$, $\neq$)

Equality ($x = y$): $v \in D(x), v \notin D(y) \longrightarrow v \notin D(x)$

• Iterate over $D(x)$
• For each $v$, check whether $v \in D(y)$ and possibly prune
• Total complexity for $x$ and $y$: $O(|D(x)| + |D(y)|)$

Disequality ($x \neq y$): $D(x) = \{v\} \longrightarrow v \notin D(y)$

• Check size of $D(x)$
• If singleton, prune
• Total complexity for $x$ and $y$: $O(1)$

Complexity of AC ($<$, $\leq$, $>$, $\geq$)

What about inequalities? E.g. $x \leq y$

Two naive filtering rules (non-symmetric for $x$ and $y$):

• $v \in D(x) \wedge v > \max(D(y)) \longrightarrow v \notin D(x)$
• $v \in D(y) \wedge v < \min(D(x)) \longrightarrow v \notin D(y)$

Complexity of AC ($<$, $\leq$, $>$, $\geq$)

What about inequalities? E.g. $x \leq y$

Two naive filtering rules (non-symmetric for $x$ and $y$):

• $v \in D(x) \wedge v > \max(D(y)) \longrightarrow v \notin D(x)$
  • Compute $\max(D(y))$
  • Iterate over $D(x)$, check and possibly prune
• $v \in D(y) \wedge v < \min(D(x)) \longrightarrow v \notin D(y)$
  • Compute $\min(D(y))$
  • Iterate over $D(y)$, check and possibly prune
• Total complexity (for $x$ and $y$): $O(|D(x)| + |D(y)|)$

Naive AC and Inequalities

Let's consider an example:

$$x \leq y, \quad x \in \{400\,000..1\,000\,000\}\, y \in \{0..500\,000\}$$

We try to apply the rule: $v \in D(x) \wedge v > \max(D(y)) \longrightarrow v \notin D(x)$

• Even assuming that $\max(D(y))$ has already been computed...
• ...We need to iterate $600\,000$ times...
• ...To conclude that $D(x)$ should be the set $\{400\,000..500\,000\}$

Naive AC and Inequalities

Let's consider an example:

$$x \leq y, \quad x \in \{400\,000..1\,000\,000\}\, y \in \{0..500\,000\}$$

We try to apply the rule: $v \in D(x) \wedge v > \max(D(y)) \longrightarrow v \notin D(x)$

• Even assuming that $\max(D(y))$ has already been computed...
• ...We need to iterate $600\,000$ times...
• ...To conclude that $D(x)$ should be the set $\{400\,000..500\,000\}$

But we could reason in another way!

• The maximum possible value for $x$ is $\max(D(y))$, i.e. $500\,000$
• Therefore, every $v \in D(x)$ s.t. $v > 500\,000$ lacks a support
• If we store the min/max of each domain explicitly, i.e. $\underline{x}, \overline{x}$...
• ...We just need to set $\overline{x} = 500\,000$, which takes only $O(1)$

Bound Consistency

We can formalize this idea:

• Step 1: for each variable (say $x$), we store the domain min/max
  • Notation: $\underline{x} \leftrightarrow \min(D(x))$, $\overline{x} \leftrightarrow \max(D(x))$
• Step 2: based on $\underline{x}$ and $\overline{x}$, we compute the min/max for $y$
  • Notation: $lb_y$ = lower bound, $ub_y$ = upper bound
• Step 3: we prune by forcing $\underline{y} = lb_y$ and $\overline{y} = ub_y$

Bound Consistency

We can formalize this idea:

• Step 1: for each variable (say $x$), we store the domain min/max
  • Notation: $\underline{x} \leftrightarrow \min(D(x))$, $\overline{x} \leftrightarrow \max(D(x))$
• Step 2: based on $\underline{x}$ and $\overline{x}$, we compute the min/max for $y$
  • Notation: $lb_y$ = lower bound, $ub_y$ = upper bound
• Step 3: we prune by forcing $\underline{y} = \max(\underline{y}, lb_y)$ and $\overline{y} = \min(\overline{y}, ub_y)$

By doing so, we enforce Bound Consistency. Formally:

By computing $ub_x, lb_x$ based on $\underline{y}, \overline{y}$ we pretend that $D(y) = \{\underline{y}..\overline{y}\}$

Bound Consistency

As an example, we consider again:

$$x \leq y, \quad x \in \{400\,000..1\,000\,000\}\, y \in \{0..500\,000\}$$

• Step 1: we just store $\underline{x}, \overline{x}, \underline{y}, \overline{y}$ explicitly
• Step 2: we compute the bounds:
  • $lb_x = -\infty$, $ub_x = \underline{y}$
  • $lb_y = \overline{x}$, $ub_y = +\infty$
• Step 3: we prune!
  • $D(x) = \{400\,000..500\,000\}$
  • $D(y) = \{400\,000..500\,000\}$
  • This is done by updating $\underline{x}, \overline{x}, \underline{y}, \overline{y}$, hence in constant time

Bound Consistency and Arc Consistency

BC is usually more efficient than AC, but also weaker

I.e. BC may prune fewer values. Consider this example:

$$x = y, \quad x \in \{0, 2, 4, 6\}\, y \in \{2, 3, 4\}$$

The bounds are:

• $lb_x = \underline{y} = 2$, $ub_x = \overline{y} = 4$
• $lb_y = \underline{x} = 0$, $ub_y = \overline{x} = 6$

We prune by updating the bounds:

• $D(x) = \{2, 4\}$, i.e. we keep the values between the bounds
• $D(y) = \{2, 3, 4\}$, even if the value $3$ is infeasible!

In general, be careful when there are "holes" in the domains

BC and AC: Wrap Up

So, overall we have that:

• AC is the best that we can do, but may be inefficient
• BC is much more efficient, but may prune less

Both AC and BC are incomplete: we still need search

• With AC, we spend more time on propagation, less time in search
• With BC, we have faster propagation, but we need to search more

It is a trade-off!

• In some cases, one approach is usually better
  • E.g. BC for $\leq$, $=$ or (next slides) arithmetic constraints
• In other cases, the answer is not trivial
  • Many CP solvers allow to choose which filtering algorithm to use

Constraint Systems

Generalized AC, BC
and Arithmetic Constraints

Troubles Ahead

And what about the arithmetic constraints? E.g.

$$z = x + y$$

Can we derive filtering rules by relying on (e.g.) AC?

Troubles Ahead

And what about the arithmetic constraints? E.g.

$$z = x + y$$

Can we derive filtering rules by relying on (e.g.) AC?

Yes, but we have a problem:

• The constraint is not binary...
• ...So, our AC definition does not apply

We need another generalization

(Generalized) Support

• Let $c$ be a constraint with scope $X(c) = \{x_0, x_1, \ldots x_{m-1}\}$
• We say that a value $v \in D(x_i)$ has a (generalized) support...
• ...if it can be extended to feasible assignment of $c$

Formally:

• We are assuming that $c$ is specified as a list of tuples
• For binary constraints, the defininition boils down to our old one

Generalized Arc Consistency

And then we just repeat the same old story:

• We can prune all and only the values that lack a support.
• Once we are done, Generalized Arc Consistency holds for $c$

• Every $x_i = v$ can be extended to feasible assignment for $c$
• But GAC is still a local form of consistency
• Hence the guarantee does not hold for multiple constraints

GAC for Sum Constraints

Let us apply the definition to (e.g.) the sum constraint

$$z = x + y$$

Basic idea (for $z$, the other rules are similar):

• Consider values $v$ in $D(z)$
• Look for values $w,u$ in $D(x), D(y)$ such that $v = w + u$
• If none is found, prune

GAC for Sum Constraints

Let us apply the definition to (e.g.) the sum constraint

$$z = x + y$$

Basic idea (for $z$, the other rules are similar):

• Consider values $v$ in $D(z)$
• Look for values $w,u$ in $D(x), D(y)$ such that $v = w + u$
• If none is found, prune

• for $v \in D(z)$:
• for $w \in D(x)$:
• if $v - w \in D(y)$: #a support is found
• break #move to next value
• prune $v$ from $D(z)$ #reached only if no support found

• Complexity: $O(|D(z)|\,|D(x)|)$

Troubles Ahead (Again)

So, our optimized complexity is:

If the domains are large we are in big trouble. E.g.:

$$z = x + y, \quad x, y \in \{0..1\,000\}, z \in \{0..10\,000\}$$

• After GAC is enforced, we have a domain reduction:

$$x \in \{0..1,000\}, y \in \{0..1,000\}, z \in \{0..2,000\}$$

• However, filtering can take up to $12\,000\,000$ steps!

Generalized Bound Consistency

The main idea is the same as in binary constraints:

• Based on the $\underline{x}_j, \overline{x}_j$ values, we compute bounds
• We used the bounds to prune other $\underline{x}_i, \overline{x}_i$

Formally, for a constraint $c$ with $X(c) = \{x_0, x_1, \ldots x_{m-1}\}$:

BC for Sum Constraints

As an example, let us consider the sum constraint

$$z = x + y$$

The bounds are:

• $lb_z = \underline{x} + \underline{y}$, $ub_z = \overline{x} + \overline{y}$
• $lb_x = \underline{z} - \overline{y}$, $ub_x = \overline{z} - \underline{y}$ (based on the fact that $x = z - y$)
• $lb_y = \underline{z} - \overline{x}$, $ub_y = \overline{z} - \underline{x}$

The whole computation is done in $O(1)$ (constant time!)

• If the domains are large, the performance gap is huge
• Moreover, if there aren't holes in the domains, the filtering is exact
  • Don't get used to this: it holds only for a few constraints...
• For this reason, BC is typically enforced with arithmetic constraints

BC for Minimum Constraints

As a second example, we consider the minimum constraint

$$z = \min(x, y)$$

The bounds are:

• $lb_z = \min(\underline{x}, \underline{y})$
• $ub_z = \min(\overline{x}, \overline{y})$
• $lb_x = \underline{z}$ (the same reasoning holds for $lb_y$)
• $ub_x = \overline{z} \text{ if } (\underline{y} > \overline{x} \vee \underline{y} > \overline{z}) \text{ else } +\infty$ (the same holds for $ub_y$)
  • The first condition means that $y$ cannot be the minimum

Examples (filtering on $z$):

$z \in \{-3..3\}, x \in \{-1..4\}, y \in \{0..4\} \longrightarrow$ $z \in \{-1..3\}$

$z \in \{0..3\}, x \in \{-1..2\}, y \in \{0..4\} \longrightarrow$ $z \in \{0..2\}$

BC for Minimum Constraints

As a second example, we consider the minimum constraint

$$z = \min(x, y)$$

The bounds are:

• $lb_z = \min(\underline{x}, \underline{y})$
• $ub_z = \min(\overline{x}, \overline{y})$
• $lb_x = \underline{z}$ (the same reasoning holds for $lb_y$)
• $ub_x = \overline{z} \text{ if } (\underline{y} > \overline{x} \vee \underline{y} > \overline{z}) \text{ else } +\infty$ (the same holds for $ub_y$)
  • The first condition means that $y$ cannot be the minimum

Examples (filtering on $x$):

$z \in \{0..2\}, x \in \{0..5\}, y \in \{3..4\} \longrightarrow$ $x \in \{0..2\}$

$z \in \{0..2\}, x \in \{-1..3\}, y \in \{-2..4\} \longrightarrow$ $x \in \{0..3\}$

Constraint Systems

Optimization in CP

Constraint Optimization Problem

A Constraint Optimization Problem (COP) is defined as:

$$COP = \langle X, D, C, f \rangle$$

where:

• $X, D, C$ are the same as in CSPs
• $f$ is an expression, called objective function
• Goal: minimize $f$ (maximization by $f$ with $-f$)

Long story short:

• A COP is just CSP with an objective function

Optimal Map Coloring

Let us consider our old map coloring example:

Optimal Map Coloring

Variables (and domains):

• $x_i \in \{0..n-1\},\quad \forall i = 0..n-1$
• $n$ is the number of regions
• $n$ is an upper bound on the number of colors!

Optimal Map Coloring

Variables (and domains):

• $x_i \in \{0..n-1\},\quad \forall i = 0..n-1$
• $n$ is the number of regions
• $n$ is an upper bound on the number of colors!

Constraints:

• $x_i \neq x_j, \forall i,j \in 0..n-1$ if region $i$ touches region $j$

Optimal Map Coloring

Variables (and domains):

• $x_i \in \{0..n-1\},\quad \forall i = 0..n-1$
• $n$ is the number of regions
• $n$ is an upper bound on the number of colors!

Constraints:

• $x_i \neq x_j, \forall i,j \in 0..n-1$ if region $i$ touches region $j$

Objective function:

• $\displaystyle f(x) = \max_{i=0..n-1} (x_i)\quad$ (can be implemented via binary $\max$)

How Do We Solve a COP?

How do we solve a COP?

• There are several approaches...
• ...But typically, we use branch & bound

Branch and Bound:

A single, simple, trick:

• Whenever we find a solution, with value $f^*$...
• ...We post a new bounding constraint in the form $f(x) < f^*$

I.e. the next solution must improve over $f^*$

• The new constraint is permanent:
• It must be satisfied by every subsequent solution

Branch and Bound Example

• Here's our optimal map coloring problem
• This is the domain state at the root of the search tree

Branch and Bound Example

• Pick first unbound variable (i.e. $x_0$)
• Post $x_0 = 1$ and propagate

Branch and Bound Example

• Pick first unbound variable (i.e. $x_1$)
• Post $x_1 = 2$ and propagate
• The domain of $f(x) = \max_{i=0..7}(x_i)$ is also updated

Branch and Bound Example

• Keep branching until we find the first solution
• The value of $f(x)$ is 4

Branch and Bound Example

• Backtrack (and restore the domains)

Branch and Bound Example

• Backtrack (and restore the domains)
• Post a new, permanent, bounding constraint $f(x) < 4$

Branch and Bound Example

• Backtrack (and restore the domains)
• Post a new, permanent, bounding constraint $f(x) < 4$
• Propagate

Branch and Bound Example

• We have a domain wipeout in $f(x)$ and $x_6$

Branch and Bound Example

• Backtrack (and restore the domains)

Branch and Bound Example

• Backtrack (and restore the domains)
• Propagate the new bounding constraint
• Another domain wipeout

Branch and Bound Example

• Backtrack (and restore the domains)

Branch and Bound Example

• Backtrack (and restore the domains)
• Propagate the new bounding constraint

Branch and Bound Example

• Backtrack (and restore the domains)
• Propagate the new bounding constraint
• Until the (feasible!) fix point is reached

Branch and Bound Example

• Post the backtracking branch
• Nothing to filter here

Branch and Bound Example

• Pick first unbound variable (i.e. $x_7$)
• Post $x_7 = 1$ and propagate
• New solution, with $f(x) = 3$

Branch and Bound Example

The solution is optimal, but we don't know it (yet)!

Branch and Bound Example

• We need to finish exploring the search tree
• This step is often called optimality proof

Wrap Up: Branch & Bound

Main idea:

• Whenever we find a solution...
• ...We post a tighter bounding constraint

Some observations:

• We use basically the same basic blocks as in CSPs
  • No explicit bounding method (just the bounding constraint)
• The algorithm is complete:
  • Given enough time, we always find the optimal solution
• It is an anytime algorithm
  • We can return a solution even if we stop early
• Empirically, most of the time usually goes in the proof of optimality