Roman Barták (Charles University in Prague, Czech Republic)

DOI: 10.4018/978-1-59904-849-9.ch062

Chapter Preview

Top*Constraint Satisfaction Problem* is formally defined as a triple: a finite set of decision variables, a domain of possible values, and a finite set of constraints restricting possible combinations of values to be assigned to variables. Although the domain can be infinite, for example real numbers, frequently, a finite domain is assumed. Without lost of generality, the finite domain can be mapped to a set of integers which is the usual case in constraint solvers. This article covers finite domains only. In many problems, each variable has its own domain which is a subset of the domain from the problem definition. Such domain can be formally defined by a unary constraint. We already mentioned that constraints restrict possible combinations of values that the decision variables can take. Typically, the constraint is defined over a subset of variables, its scope, and it is specified either extensionally, as a set of value tuples satisfying the constraint, or intentionally, using a logical or arithmetical formula. This formula, for example A < B, then describes which value tuples satisfy the constraint. A small example of a CSP is ({A, B, C}, {1, 2, 3}, {A < B, B < C}).

The task of constraint processing is to instantiate each decision variable by a value from the domain in such a way that all constraints are satisfied. This instantiation is called a *feasible assignment*. Clearly, the problem whether there exists a feasible assignment for a CSP is NP-complete – problems like 3SAT or knapsack problem (Garey & Johnson, 1979) can be directly encoded as CSPs. Sometimes, the core constraint satisfaction problem is accompanied by a so called objective function defined over (some) decision variables and we get a *Constrained Optimisation Problem*. Then the task is to select among the feasible assignments the assignment that minimizes (or maximizes) the value of the objective function. This article focuses on techniques for finding a feasible assignment but these techniques can be naturally extended to optimization problems via a well-known branch-and-bound technique (Van Hentenryck, 1989).

Decision Variable: A variable modelling some feature of the problem, for example a start time of activity, whose value we are looking for in such a way that specified constraints are satisfied.

Search Algorithms: Algorithms that explore the space of possible (partial or complete) instantiations of decision variables with the goal to find an instantiation satisfying all the constraints (and optimizing the objective function in case of COP).

Domain of Variable: A set of possible values that can be assigned to a decision variable, for example a set of times when some activity can start. Constraint processing usually assumes finite domains only.

Global Constraint: An n-ary constraint modelling a subset of simpler constraints by providing a dedicated filtering algorithm that achieves stronger or faster domain pruning in comparison to making the simpler constraints (locally) consistent. All-different is an example of a global constraint.

Constraint Satisfaction Problem (CSP): A problem formulated using a set of decision variables, their domains, and constraints between the variables. The task is to find an instantiation of decision variables by values from their domains in such a way that all the constraints are satisfied.

Constraint: Any relation between a subset of decision variables. Can be expressed extensionally, as a set of value tuples satisfying the constraint, or intentionally, using an arithmetical or logical formula between the variables, for example A+B?

Constrained Optimisation Problem (COP): A Constraint Satisfaction Problem extended by an objective function over the (subset of) decision variables. The task is to find a solution to the CSP which minimizes or maximizes the value of the objective function.

Domain Pruning (Filtering): A process of removing values from domains of variables that cannot take part in any solution. Usually, due to efficiency issues only the values locally violating some constraint are pruned. It is the most common type of consistency technique.

Consistency Techniques: Techniques that remove inconsistent values (from variables’ domains) or value tuples, that is, the values that cannot be assigned to a given variable in any solution. Arc consistency is the most widely used consistency technique.

Look Ahead: The most common technique for integrating depth-first search with maintaining consistency. Each time a search decision is done, it is propagated in the problem model by making the model consistent.

Search this Book:

Reset