1. Problems related to CP

• 8-Queens Problems
• Map Coloring

1.1 Computational paradigm

• use constraints to reduce the set of values that each variable can take
• make a choice when no more deduction can be performed.
• The method we use:
  • Branch and prune:
  • Pruning: use constraints to remove, from the variable domains, values that cannot belong to any solution
  • Branching: e.g. try all possible values of a variable until a solution is found or it can be proven that no solution exists.

Constraints task:

• Feasibility checking: if it can be satisfied given the values in the domains of its variables
• Pruning: if satisfiable, then a constraint determines which values in the domain cannot be a part of any solution.

 
propagate()
{
  repeat
    select a constraint c;
    if c is infeasible given the domain store then
      return failure;
    else
      apply the pruning algorithm associated with c;
  until no constraint can remove any value from the
  domain of its variables;
  return success;
}

2.Complex Constraint Propagation

Actually, for every constraint propagation, lies specific algorithm behind the scene. Here is an example widely used.

Consider a linear constraint:

$$\sum_{i=1}^n a_ix_i \ge \sum_{i=1}^m b_iy_i$$

also, $a_i, b_i \ge 0$ are constant;
$x_i, y_i$ are variables with domains $D(x_i), D(y_i)$.

Then we introduce the feasibility test:

$$\sum_{i=1}^n a_i\max(D(x_i))\ge \sum_{i=1}^m b_i \min(D(y_i))$$

then we suppose:

$$l=\sum_{i=1}^n a_i\max(D(x_i))\\ r=\sum_{i=1}^m b_i \min(D(y_i)) $$

Then the pruning would be:

$$a_ix_i\ge r-(l-a_i\max(D(x_i)))$$

which is,

$$x_{i} \geq\left\lceil\frac{r-\left(l-a_{i} \max \left(D\left(x_{i}\right)\right))\right.}{a_{i}}\right\rceil \quad y_{j} \leq\left\lfloor\frac{l-\left(r-b_{j} \min \left(D\left(y_{j}\right)\right))\right.}{b_{j}}\right\rfloor$$

3. Element constraint, stable marriage, magic series

Magic Series

A series $S = (S_0, \cdots, S_n)$ is magic if $S_i$ represents the number of occurrences of $i$ in $S$, for example:

$$S = (2, 1, 2, 0, 0)$$

Reification

The ability to convert a constraint into a boolean format.

Stable Marriages