Constraint Optimization

Constraint optimization is a useful framework for modelling and solving many combinatorial optimization problems. It is central in mutiple Artificial Intelligence problems, especially in areas related to scheduling, logistics and planning.


A constraint optimization problem (COP) involves a finite set of variables, each taking a value in a finite domain. Variables are related by cost functions that definen the cost of value tuples on some variables subsets. A solution is a complete tuple with acceptable overall cost, and it is optimal if its overall cost is minimal. Solving COP optimally is known to be NP-hard.