The value of CP lies

in the constraints

We only saw two basic binary constraints.

But there are hundreds of them.

Why are there so many of them?

Is it not possible to do with less?

Indeed, MILP and SAT are doing very well with one type of constraint !

Two main reasons

  1. Modeling : stronger expressive power
  2. Solving : increased filter quality

At the modeling stage

  • each constraint is semantically defined
  • which also indicates the contract it guarantees

Examples

Name Purpose
alldifferent enforces all variables in its scope to take distinct values
increasing the variables in its scope are increasing
maximum a variable is the maximum value of a collection of variables
…

Others are less obvious 😇

subgraph_isomorphism, path, diffn, geost, …

but are documented

At the modeling stage (2/2)

  • A CSP model is a conjunction of constraints
  • The model can be very compact
  • It is easy to understand and modify a model

Recall that there are modelling languages to do this

At solving stage

But it is rather here that one can measure the interest of the constraints

A constraint captures a sub-problem

and provides an efficient way to deal with it

thanks to an adapted filtering algorithm

On one example

$\bigwedge_{X_i,X_j \in X, i\neq j} X_i \neq X_j$

-vs-

$\texttt{allDifferent}(X)$

Both version find the same solutions

but the 2nd filters more

With binary constraints

Alt text.

What can be deduced?

Nothing until a variable is set

With a global constraint

Alt text.

Rely on graph theory…

With a global constraint

Alt text.

pair variables and values in a bipartite graph…

With a global constraint

Alt text.

find maximum cardinality matchings…

With a global constraint

Alt text.

remove values which belong to none of them.

Summary

$\bigwedge_{x_i,x_j \in X, i\neq j} x_i \neq x_j$ $\texttt{allDifferent}(X)$
#cstrs $\frac{\vert X \vert \times \vert X\vert -1}{2}$ 1
Filtering weak and late arc-consistency in polynomial time and space
Algorithm straightforward tricky*

*: but already done for you in libraries

Remarks about global constraints

Many model highly combinatorial problems

It is likely that:

  • arc-consistency is not reached (i.e., weaker filtering)
  • filtering is complex to achieve

Their expressive power remains strong