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.

Copyright © 2008 by SAS Institute Inc., Cary, NC, USA. All rights reserved.