Previous Page | Next Page

The CLP Procedure

The Constraint Satisfaction Problem

Many important problems in areas such as artificial intelligence (AI) and operations research (OR) can be formulated as constraint satisfaction problems. A CSP is defined by a finite set of variables taking values from finite domains and a finite set of constraints restricting the values the variables can simultaneously take.

More formally, a CSP can be defined as a triple :

  • is a finite set of variables.

  • is a finite set of domains, where is a finite set of possible values that the variable can take. is known as the domain of variable .

  • is a finite set of constraints restricting the values that the variables can simultaneously take.

Note that the domains need not represent consecutive integers. For example, the domain of a variable could be the set of all even numbers in the interval [0, 100]. A domain does not even need to be totally numeric. In fact, in a scheduling problem with resources, the values are typically multidimensional. For example, an activity can be considered as a variable, and each element of the domain would be an n-tuple that represents a start time for the activity as well as the resource(s) that must be assigned to the activity corresponding to the start time.

A solution to a CSP is an assignment of values to the variables in order to satisfy all the constraints, and the problem amounts to finding solution(s), or possibly determining that a solution does not exist.

The CLP procedure can be used to find one or more (and in some instances, all) solutions to a CSP with linear, logical, global, and scheduling constraints. The numeric components of all variable domains are assumed to be integers.

Note: This procedure is experimental.

Previous Page | Next Page | Top of Page