Constraint programming

related:: Machine Learning

An Introduction To Constraint Programming - Jacob Allen

Constraint satisfaction problem

Give:

  • Variables to make decisions on
  • For each variable, a domain of possible values
  • Constraints on the variables

Find:

  • Assign values to variables with all constraints satisfied

Constraint propagation

If a variable can only hold one valid value, assign that value.

Constraint optimisation problems

A Constraint satisfaction problem, with soft constraints. Soft constraints are used to determine the quality of the solution. Similar to a loss function (Machine Learning), this is called the objective function.

Modelling the problem

  • Our effort is not spend on solving the problem, but defining it. It’s Declarative programming.
  • Domains need to be finite.
  • Variables are usually booleans, integers or sequences of integers. The types are very limited compared to other programming languages.