they provide a local view of the problem – connect only a few variables
can be heterogeneous (domains can be different; they don't have to be linear constraints)
are non-directional (left-hand side and right-hand side have no special meaning)
are declarative (they don't tell you how to satisfy them)
are additive (their order is not important; we care about their conjunction)
are rarely independent (they share variables)
advantages of CP
close to real-life problems
declarative manner (we can focus on problem description without paying too much attention to problem solving)
co-operative problem solving (we can integrate various solving approaches – Gaussian elimination for linear inequalities, bipartite graph matching for combinatorial constraints, …)
semantic foundation (we can use clean and elegant modelling languages)
limitations of CP
efficiency (combinatorial explosion, many problems are NP-complete)
hard-to-predict behaviour (it's hard to estimate the efficiency before running the model on real data)
model stability (new data = new problem)
too local (individual constraints give a very limited insight – one constraint may look satisfiable even though the whole model is not)
weak co-operation of solvers (usually done only through sharing variables)
binary CSP
CSP where all the constraints are binary
note: unary constraints can be encoded into domains directly
dual encoding: k-ary constraint can be converted to a dual variable with the domain consisting of compatile tuples
Hurá, máš hotovo! 🎉 Pokud ti moje kartičky pomohly, můžeš mi koupit limonádu.