 Constraint satisfaction

In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that satisfies all constraints.
The techniques used in constraint satisfaction depend on the kind of constraints being considered. Often used are constraints on a finite domain, to the point that constraint satisfaction problems are typically identified with problems based on constraints on a finite domain. Such problems are usually solved via search, in particular a form of backtracking or local search. Constraint propagation are other methods used on such problems; most of them are incomplete in general, that is, they may solve the problem or prove it unsatisfiable, but not always. Constraint propagation methods are also used in conjunction with search to make a given problem simpler to solve. Other considered kinds of constraints are on real or rational numbers; solving problems on these constraints is done via variable elimination or the simplex algorithm.
Constraint satisfaction originated in the field of artificial intelligence in the 1970s (see for example (Laurière 1978)). During the 1980s and 1990s, embedding of constraints into a programming language were developed. Languages often used for constraint programming are Prolog and C++.
Contents
Constraint satisfaction problem
Main article: Constraint satisfaction problemAs originally defined in artificial intelligence, constraints enumerate the possible values a set of variables may take. Informally, a finite domain is a finite set of arbitrary elements. A constraint satisfaction problem on such domain contains a set of variables whose values can only be taken from the domain, and a set of constraints, each constraint specifying the allowed values for a group of variables. A solution to this problem is an evaluation of the variables that satisfies all constraints. In other words, a solution is a way for assigning a value to each variable in such a way that all constraints are satisfied by these values.
In some circumstances, there may exist additional requirements: one may be interested not only in the solution (and in the fastest or most computationally efficient way to reach it) but in how it was reached; e.g. one may want the "simplest" solution ("simplest" in a logical, non computational sense that has to be precisely defined). This is often the case in logic games such as Sudoku.
In practice, constraints are often expressed in compact form, rather than enumerating all values of the variables that would satisfy the constraint. One of the most used constraints is the one establishing that the values of the affected variables must be all different.
Problems that can be expressed as constraint satisfaction problems are the Eight queens puzzle, the Sudoku solving problem, the Boolean satisfiability problem, scheduling problems and various problems on graphs such as the graph coloring problem.
While usually not included in the above definition of a constraint satisfaction problem, arithmetic equations and inequalities bound the values of the variables they contain and can therefore be considered a form of constraints. Their domain is the set of numbers (either integer, rational, or real), which is infinite: therefore, the relations of these constraints may be infinite as well; for example, X = Y + 1 has an infinite number of pairs of satisfying values. Arithmetic equations and inequalities are often not considered within the definition of a "constraint satisfaction problem", which is limited to finite domains. They are however used often in constraint programming.
Solving
Constraint satisfaction problems on finite domains are typically solved using a form of search. The most used techniques are variants of backtracking, constraint propagation, and local search. These techniques are used on problems with nonlinear constraints.
In case there is a requirement on "simplicity", a pure logic, pattern based approach was first introduced for the Sudoku CSP in the book The Hidden Logic of Sudoku^{[1]}. It has recently been generalized to any finite CSP in another book by the same author: Constraint Resolution Theories^{[2]}.
Variable elimination and the simplex algorithm are used for solving linear and polynomial equations and inequalities, and problems containing variables with infinite domain. These are typically solved as optimization problems in which the optimized function is the number of violated constraints.
Complexity
Main article: Complexity of constraint satisfactionSolving a constraint satisfaction problem on a finite domain is an NP complete problem with respect to the domain size. Research has shown a number of tractable subcases, some limiting the allowed constraint relations, some requiring the scopes of constraints to form a tree, possibly in a reformulated version of the problem. Research has also established relationship of the constraint satisfaction problem with problems in other areas such as finite model theory.
A very different aspect of complexity appears when one fixes the size of the domain. It is about the complexity distribution of minimal instances of a CSP of fixed size (e.g. Sudoku(9x9)). Here, complexity is measured according to the abovementioned "simplicity" requirement (see Unbiased Statistics of a CSP  A ControlledBias Generator'^{[3]} or Constraint Resolution Theories^{[2]}). In this context, a minimal instance is an instance with a unique solution such that if any given (or clue) is deleted from it, the resulting instance has several solutions (statistics can only be meaningful on the set of minimal instances).
Constraint programming
Main article: Constraint programmingConstraint programming is the use of constraints as a programming language to encode and solve problems. This is often done by embedding constraints into a programming language, which is called the host language. Constraint programming originated from a formalization of equalities of terms in Prolog II, leading to a general framework for embedding constraints into a logic programming language. The most common host languages are Prolog, C++, and Java, but other languages have been used as well.
Constraint logic programming
Main article: Constraint logic programmingA constraint logic program is a logic program that contains constraints in the bodies of clauses. As an example, the clause
A(X):X>0,B(X)
is a clause containing the constraintX>0
in the body. Constraints can also be present in the goal. The constraints in the goal and in the clauses used to prove the goal are accumulated into a set called constraint store. This set contains the constraints the interpreter has assumed satisfiable in order to proceed in the evaluation. As a result, if this set is detected unsatisfiable, the interpreter backtracks. Equations of terms, as used in logic programming, are considered a particular form of constraints which can be simplified using unification. As a result, the constraint store can be considered an extension of the concept of substitution that is used in regular logic programming. The most common kinds of constraints used in constraint logic programming are constraints over integers/rational/real numbers and constraints over finite domains.Concurrent constraint logic programming languages have also been developed. They significantly differ from nonconcurrent constraint logic programming in that they are aimed at programming concurrent processes that may not terminate. Constraint handling rules can be seen as a form of concurrent constraint logic programming, but are also sometimes used within a nonconcurrent constraint logic programming language. They allow for rewriting constraints or to infer new ones based on the truth of conditions.
Constraint satisfaction toolkits
Constraint satisfaction toolkits are software libraries for imperative programming languages that are used to encode and solve a constraint satisfaction problem.
 Cassowary constraint solver is an open source project for constraint satisfaction (accessible from C, Java, Python and other languages).
 Comet, a commercial programming language and toolkit
 Gecode, an open source portable toolkit written in C++ developed as a productionquality and highly efficient implementation of a complete theoretical background.
 JaCoP (solver) an open source Java constraint solver
 Koalog a commercial Javabased constraint solver.
 logilabconstraint an open source constraint solver written in pure Python with constraint propagation algorithms.
 MINION an opensource constraint solver written in C++, with a small language for the purpose of specifying models/problems.
 ZDC is an open source program developed in the ComputerAided Constraint Satisfaction Project for modelling and solving constraint satisfaction problems.
Other constraint programming languages
Constraint toolkits are a way for embedding constraints into an imperative programming language. However, they are only used as external libraries for encoding and solving problems. An approach in which constraints are integrated into an imperative programming language is taken in the Kaleidoscope programming language.
Constraints have also been embedded into functional programming languages.
See also
 Constraint satisfaction problem
 Constraint (mathematics)
 Candidate solution
 Boolean satisfiability problem
 Decision theory
 Satisfiability modulo theories
References
 ^ (English)Berthier, Denis (16 mai 2007). Lulu Publishers, ISBN 9781847534729. http://www.carva.org/denis.berthier/HLS. Retrieved 16 mai 2007.
 ^ ^{a} ^{b} (English)Berthier, Denis (5 octobre 2011). Lulu Publishers, ISBN 9781447868880. http://www.carva.org/denis.berthier/CRT. Retrieved 5 octobre 2011.
 ^ Denis Berthier, Unbiased Statistics of a CSP  A ControlledBias Generator, International Joint Conferences on Computer, Information, Systems Sciences and Engineering (CISSE 09), December 412, 2009
 Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press. ISBN 0521825830.
 Berthier, Denis (2011). Constraint Resolution Theories. Lulu. ISBN 9781447868880. http://www.carva.org/denis.berthier/CRT.
 Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 1558608907. http://www.ics.uci.edu/~dechter/books/index.html.
 Dincbas, M.; Simonis, H.; Van Hentenryck, P. (1990). "Solving Large Combinatorial Problems in Logic Programming". Journal of logic programming 8 (1–2): 75–93. doi:10.1016/07431066(90)900527.
 Freuder, Eugene; Alan Mackworth (ed.) (1994). Constraintbased reasoning. MIT Press.
 Frühwirth, Thom; Slim Abdennadher (2003). Essentials of constraint programming. Springer. ISBN 3540676236.
 Guesguen, Hans; Hertzberg Joachim (1992). A Perspective of Constraint Based Reasoning. Springer. ISBN 9783540555100.
 Jaffar, Joxan; Michael J. Maher (1994). "Constraint logic programming: a survey". Journal of logic programming 19/20: 503–581. doi:10.1016/07431066(94)900337.
 Laurière, JeanLouis (1978). "A Language and a Program for Stating and Solving Combinatorial Problems". Artificial intelligence 10 (1): 29–127. doi:10.1016/00043702(78)900292.
 Lecoutre, Christophe (2009). Constraint Networks: Techniques and Algorithms. ISTE/Wiley. ISBN 9781848211063. http://www.iste.co.uk/index.php?f=a&ACTION=View&id=250.
 Marriot, Kim; Peter J. Stuckey (1998). Programming with constraints: An introduction. MIT Press. ISBN 0262133415.
 Rossi, Francesca; Peter van Beek, Toby Walsh (ed.) (2006). Handbook of Constraint Programming,. Elsevier. ISBN 9780444527264 0444527265. http://www.elsevier.com/wps/find/bookdescription.cws_home/708863/description#description.
 Tsang, Edward (1993). Foundations of Constraint Satisfaction. Academic Press. ISBN 0127016104. http://www.bracil.net/edward/FCS.html.
 Van Hentenryck, Pascal (1989). Constraint Satisfaction in Logic Programming. MIT Press. ISBN 0262081814.
External links
Categories:
Wikimedia Foundation. 2010.
См. также в других словарях:
Constraint satisfaction problem — Constraint satisfaction problems (CSP)s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite… … Wikipedia
Constraint satisfaction dual problem — The dual problem is a reformulation of a constraint satisfaction problem expressing each constraint of the original problem as a variable. Dual problems only contain binary constraints, and are therefore solvable by algorithms tailored for such… … Wikipedia
Constraint Satisfaction Problem — Ein Constraint Satisfaction Problem (Bedingungserfüllungsproblem, abgekürzt CSP) ist eine Aufgabenstellung aus der künstlichen Intelligenz und aus dem Operations Research. Aufgabe ist es, einen Zustand (d. h. Belegungen von Variablen) zu finden,… … Deutsch Wikipedia
ConstraintSatisfactionProblem — Ein Constraint Satisfaction Problem (dt.: Bedingungserfüllungsproblem, abgekürzt CSP) ist eine Aufgabenstellung aus der künstlichen Intelligenz und aus dem Operations Research. Aufgabe ist es, einen Zustand (d. h. Belegungen von Variablen) zu… … Deutsch Wikipedia
Complexity of constraint satisfaction — The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction… … Wikipedia
Decomposition method (constraint satisfaction) — In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a… … Wikipedia
Hybrid algorithm (constraint satisfaction) — In constraint satisfaction, a hybrid algorithm solves a constraint satisfaction problem by the combination of two different methods, for example variable conditioning (backtracking, backjumping, etc.) and constraint inference (arc consistency,… … Wikipedia
Local search (constraint satisfaction) — In constraint satisfaction, local search is an incomplete method for finding a solution to a problem. It is based on iteratively improving an assignment of the variables until all constraints are satisfied. In particular, local search algorithms… … Wikipedia
Constraint — is an element factor or a subsystem that works as a bottleneck. It restricts an entity, project, or system (such as a manufacturing or decision making process) from achieving its potential (or higher level of output) with reference to its goal.… … Wikipedia
Constraint Composite Graph — The constraint composite graph is a node weighted undirected graph associated with a given combinatorial optimization problem posed as a weighted constraint satisfaction problem. Developed and introduced by Satish Kumar Thittamaranahalli (T. K.… … Wikipedia