Lecture

• problem
  • variables
  • domains
  • constraints
• a feasible solution = a complete consistent assignment of values to variables
• an optimal solution = a feasible solution that minimizes/maximizes a value of some objective function
• properties of constraints
  • they express partial information
  • 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