 Constraint programming

Programming paradigms  Agentoriented
 Automatabased
 Componentbased
 Concatenative
 Concurrent computing
 Relativistic programming
 Datadriven
 Declarative (contrast: Imperative)
 Constraint
 Dataflow
 Celloriented (spreadsheets)
 Reactive
 Logic
 Abductive logic
 Answer set
 Constraint logic
 Functional logic
 Inductive logic
 Eventdriven
 Expressionoriented
 Featureoriented
 Functionlevel (contrast: Valuelevel)
 Functional
 Generic
 Imperative (contrast: Declarative)
 Languageoriented
 Metaprogramming
 Nonstructured (contrast: Structured)
 Nondeterministic
 Parallel computing
 Programming in the large / small
 Semantic
 Structured (contrast: Nonstructured)
 Modular (contrast: Monolithic)
 Objectoriented
 Recursive
 Valuelevel (contrast: Functionlevel)
Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. This makes constraint programming a form of declarative programming. The constraints used in constraint programming are of various kinds: those used in constraint satisfaction problems (e.g. "A or B is true"), those solved by the simplex algorithm (e.g. "x ≤ 5"), and others. Constraints are usually embedded within a programming language or provided via separate software libraries.
Constraint programming began with constraint logic programming, which embeds constraints into a logic program. This variant of logic programming is due to Jaffar and Lassez, who extended in 1987 a specific class of constraints that were introduced in Prolog II. The first implementations of constraint logic programming were Prolog III, CLP(R), and CHIP.
Other than logic programming, constraints can be mixed with functional programming, term rewriting, and imperative languages. Programming languages with builtin support for constraints include Oz (functional programming) and Kaleidoscope (imperative programming). Mostly, constraints are implemented in imperative languages via constraint solving toolkits, which are separate libraries for an existing imperative language.
Contents
Constraint logic programming
Main article: Constraint logic programmingConstraint programming is an embedding of constraints in a host language. The first host languages used were logic programming languages, so the field was initially called constraint logic programming. The two paradigms share many important features, like logical variables and backtracking. Today most Prolog implementations include one or more libraries for constraint logic programming.
The difference between the two is largely in their styles and approaches to modeling the world. Some problems are more natural (and thus, simpler) to write as logic programs, while some are more natural to write as constraint programs.
The constraint programming approach is to search for a state of the world in which a large number of constraints are satisfied at the same time. A problem is typically stated as a state of the world containing a number of unknown variables. The constraint program searches for values for all the variables.
Temporal concurrent constraint programming (TCC) and nondeterministic temporal concurrent constraint programming (NTCC) are variants of constraint programming that can deal with time.
Some popular constraint logic languages are:
 BProlog (Prolog based, proprietary)
 CHIP V5 (Prolog based, also includes C++ and C libraries, proprietary)
 Ciao (Prolog based, Free software: GPL/LGPL)
 ECLiPSe (Prolog based, open source)
 SICStus (Prolog based, proprietary)
 GNU Prolog (free software)
 Oz
 YAP Prolog
 SWI Prolog a free Prolog system containing several libraries for constraint solving
 Claire
 Curry (Haskell based, with free implementations)
 Turtle (free software: GPL)
Domains
The constraints used in constraint programming are typically over some specific domains. Some popular domains for constraint programming are:
 boolean domains, where only true/false constraints apply (SAT problem)
 integer domains, rational domains
 linear domains, where only linear functions are described and analyzed (although approaches to nonlinear problems do exist)
 finite domains, where constraints are defined over finite sets
 mixed domains, involving two or more of the above
Finite domains is one of the most successful domains of constraint programming. In some areas (like operations research) constraint programming is often identified with constraint programming over finite domains.
All of the above examples are commonly solved by satisfiability modulo theories (SMT) solvers.
Finite domain solvers are useful for solving constraint satisfaction problems, and are often based on arc consistency or one of its approximations.
The syntax for expressing constraints over finite domains depends on the host language. The following is a Prolog program that solves the classical alphametic puzzle SEND+MORE=MONEY in constraint logic programming:
sendmore(Digits) : Digits = [S,E,N,D,M,O,R,Y], % Create variables Digits :: [0..9], % Associate domains to variables S #\= 0, % Constraint: S must be different from 0 M #\= 0, alldifferent(Digits), % all the elements must take different values 1000*S + 100*E + 10*N + D % Other constraints + 1000*M + 100*O + 10*R + E #= 10000*M + 1000*O + 100*N + 10*E + Y, labeling(Digits). % Start the search
The interpreter creates a variable for each letter in the puzzle. The symbol
::
is used to specify the domains of these variables, so that they range over the set of values {0,1,2,3, ..., 9}. The constraintsS#\=0
andM#\=0
means that these two variables cannot take the value zero. When the interpreter evaluates these constraints, it reduces the domains of these two variables by removing the value 0 from them. Then, the constraintalldifferent(Digits)
is considered; it does not reduce any domain, so it is simply stored. The last constraint specifies that the digits assigned to the letters must be such that "SEND+MORE=MONEY" holds when each letter is replaced by its corresponding digit. From this constraint, the solver infers that M=1. All stored constraints involving variable M are awakened: in this case, constraint propagation on thealldifferent
constraint removes value 1 from the domain of all the remaining variables. Constraint propagation may solve the problem by reducing all domains to a single value, it may prove that the problem has no solution by reducing a domain to the empty set, but may also terminate without proving satisfiability or unsatisfiability. The labeling literals are used to actually perform search for a solution.Constraint programming libraries for imperative programming languages
Constraint programming is often realized in imperative programming via a separate library. Some popular libraries for constraint programming are:
 Artelys Kalis (C++ library, XpressMosel module, proprietary)
 Choco (Java library, free software: X11 style)
 Comet (C style language for constraint programming, constraintbased local search and mathematical programming, free binaries available for academic use)
 Cream (Java library, free software: LGPL)
 Disolver (C++ library, proprietary)
 Drools Planner (Java, open source, ASL)
 Emma (Python library, proprietary)
 Gecode (C++ library, free software: X11 style)
 Google CP Solver (Python, Java, and C++ library, Apache license)
 IBM ILOG CP (C++ library, proprietary) and CP Optimizer (C++, Java, .NET libraries, proprietary) successor^{[1]} of ILOG Solver, which was considered the market leader in commercial constraint programming software as of 2006^{[2]}
 JaCoP (Java library, open source) available here
 JOpt (Java library, free software)
 JSR331 (Java Constraint Programming API, JCP standard)
 Koalog Constraint Solver (Java library, proprietary)
 Minion (C++ program, GPL)
 pythonconstraint (Python library, GPL)
 Turtle++ (C++ library  inspired by the Turtle Language, free software)
Some languages that support constraint programming
 Alma0 a small, strongly typed, constraint language with a limited number of features inspired by logic programming, supporting imperative programming.
 Bertrand a language for building constraint programming systems.
 Common Lisp via Screamer (a free software library which provides backtracking and CLP(R), CHiP features).
See also
 Combinatorial optimization
 Constraint satisfaction
 Constraint logic programming
 Heuristic algorithms
 Mathematical programming (Optimization theory)
 Nurse scheduling problem
 Concurrent Constraint Programming (CCP)
References
 ^ Frédéric Benhamou; Narendra Jussien; Barry O'Sullivan (2007). Trends in constraint programming. John Wiley and Sons. p. 45. ISBN 9781905209972. http://books.google.com/books?id=aS9OoJIavBYC&pg=PA45.
 ^ Francesca Rossi; Peter Van Beek; Toby Walsh (2006). Handbook of constraint programming. Elsevier. p. 157. ISBN 9780444527264. http://books.google.com/books?id=Kjap9ZWcKOoC&pg=PA157.
External links
 Information on the annual CP conference
 OnLine Guide to Constraint Programming
 Program Does Not Equal Program: Constraint Programming and its Relationship to Mathematical Programming^{[dead link]}
 Mozart (Oz based, Free software: X11 style)
 Cork Constraint Computation Centre (4C)
 Global Constraint Catalog
Categories: Constraint programming
 Programming paradigms
 Declarative programming
Wikimedia Foundation. 2010.
Look at other dictionaries:
Constraint logic programming — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computing … Wikipedia
Constraint Handling Rules — (CHR) is a declarative programming language extension introduced in 1991[1][2] by Thom Frühwirth. Originally designed for developing (prototypes of) constraint programming systems, CHR is increasingly used as a high level general purpose… … Wikipedia
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 — 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… … Wikipedia
Constraint inference — In constraint satisfaction, constraint inference is a relationship between constraints and their consequences. A set of constraints D entails a constraint C if every solution to D is also a solution to C. In other words, if V is a valuation of… … 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
Constraint graph — For a graph in electronic design automation, see Constraint graph (layout). In constraint satisfaction research of artificial intelligence and operations research, constraint graphs and hypergraphs are used to represent relations among… … Wikipedia
Constraint learning — In constraint satisfaction backtracking algorithms, constraint learning is a technique for improving efficiency. It works by recording new constraints whenever an inconsistency is found. This new constraint may reduce the search space, as future… … 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 optimization — In constraint satisfaction, constrained optimization (also called constraint optimization) seeks for a solution maximizing or minimizing a cost function. Contents 1 Definition 2 Solution methods 2.1 Branch and bound … Wikipedia