Constraint programming is a programming paradigm

Programming paradigm

A programming paradigm is a fundamental style of computer programming. Paradigms differ in the concepts and abstractions used to represent the elements of a program and the steps that compose a computation A programming paradigm is a fundamental style of computer programming. (Compare with a...

 wherein relations between variables are stated in the form of constraint

Constraint (mathematics)

In mathematics, a constraint is a condition that a solution to an optimization problem must satisfy. There are two types of constraints: equality constraints and inequality constraints...

s. Constraints differ from the common primitives of imperative programming

Imperative programming

In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...

 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

Declarative programming

In computer science, declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow. Many languages applying this style attempt to minimize or eliminate side effects by describing what the program should accomplish, rather than...

. The constraints used in constraint programming are of various kinds: those used in constraint satisfaction problem

Constraint satisfaction problem

Constraint satisfaction problems 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 constraints over variables, which is solved by constraint...

s (e.g. "A or B is true"), those solved by the simplex algorithm

Simplex algorithm

In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....

 (e.g. " ≤ 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)

CLP(R)

CLP is a declarative programming language. It stands for Constraint logic programming where real refers to the real numbers. It can be considered and is generally implemented as a superset or add-on package for a Prolog implementation.-Example Rule :...

, and CHIP.

Other than logic programming, constraints can be mixed with functional programming

Functional programming

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...

, term rewriting, and imperative languages.
Programming languages with built-in support for constraints include Oz (functional programming) and Kaleidoscope

Kaleidoscope programming language

The Kaleidoscope programming language is a constraint programming language embedding constraints into an imperative object-oriented language....

 (imperative programming). Mostly, constraints are implemented in imperative languages via constraint solving toolkits, which are separate libraries for an existing imperative language.

Constraint logic programming

Constraint programming is an embedding of constraints in a host language. The first host languages used were logic programming

Logic programming

Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...

 languages, so the field was initially called constraint logic programming. The two paradigms share many important features, like logical variables and backtracking

Backtracking

Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...

. Today most Prolog

Prolog

Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...

 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 non-deterministic temporal concurrent constraint programming (NTCC) are variants of constraint programming that can deal with time.

Some popular constraint logic languages are:

• B-Prolog (Prolog
  Prolog
  Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
  
   based, proprietary)
• CHIP V5 (Prolog based, also includes C++ and C libraries, proprietary)
• Ciao
  Ciao (programming language)
  Ciao is a general-purpose programming language which supports logic, constraint, functional, higher-order, and object-oriented programming styles. Its main design objectives are high expressive power, extensibility, safety, reliability, and efficient execution....
  
   (Prolog based, Free software: GPL/LGPL)
• ECLiPSe
  ECLiPSe
  ECLiPSe is a software system for the development and deployment of Constraint Programming applications, e.g. in the areas of optimization, planning, scheduling, resource allocation, timetabling, transport etc....
  
   (Prolog based, open source)
• SICStus (Prolog based, proprietary)
• GNU Prolog
  GNU Prolog
  GNU Prolog is a compiler developed by with an interactive debugging environment for Prolog available for Unix, Windows and Mac OS X...
  
   (free software)
• Oz
• YAP Prolog
• SWI Prolog a free
  Free software
  Free software, software libre or libre software is software that can be used, studied, and modified without restriction, and which can be copied and redistributed in modified or unmodified form either without restriction, or with restrictions that only ensure that further recipients can also do...
  
   Prolog system containing several libraries for constraint solving
• Claire
• Curry (Haskell
  Haskell (programming language)
  Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
  
   based, with free
  Free software
  Free software, software libre or libre software is software that can be used, studied, and modified without restriction, and which can be copied and redistributed in modified or unmodified form either without restriction, or with restrictions that only ensure that further recipients can also do...
  
   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
  Boolean datatype
  In computer science, the Boolean or logical data type is a data type, having two values , intended to represent the truth values of logic and Boolean algebra...
  
   domains, where only true/false constraints apply (SAT problem
  Boolean satisfiability problem
  In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
  
  )
• integer
  Integer
  The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
  
   domains, rational domains
• linear
  Linear algebra
  Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
  
   domains, where only linear
  Linear
  In mathematics, a linear map or function f is a function which satisfies the following two properties:* Additivity : f = f + f...
  
   functions are described and analyzed (although approaches to non-linear 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

Operations research

Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...

) constraint programming is often identified with constraint programming over finite domains.

All of the above examples are commonly solved by satisfiability modulo theories

Satisfiability Modulo Theories

In computer science, the Satisfiability Modulo Theories problem is a decision problem for logical formulas with respect to combinations of background theories expressed in classical first-order logic with equality...

 (SMT) solvers.

Finite domain solvers are useful for solving constraint satisfaction problem

Constraint satisfaction problem

Constraint satisfaction problems 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 constraints over variables, which is solved by constraint...

s, 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

Prolog

Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...

 program that solves the classical alphametic puzzle SEND+MORE=MONEY

Verbal arithmetic

Verbal arithmetic, also known as alphametics, cryptarithmetic, crypt-arithmetic, cryptarithm or word addition, is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters. The goal is to identify the value of each letter...

 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 constraints S#\=0 and M#\=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 constraint alldifferent(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 the alldifferent 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++
  C++
  C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
  
   library, Xpress-Mosel module, proprietary)
• Choco (Java
  Java (programming language)
  Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
  
   library, free software: X11 style)
• Comet (C
  C (programming language)
  C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
  
   style language for constraint programming, constraint-based local search and mathematical programming, free binaries available for academic use)
• Cream (Java
  Java (programming language)
  Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
  
   library, free software: LGPL)
• Disolver (C++
  C++
  C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
  
   library, proprietary)
• Drools Planner (Java, open source, ASL)
• Emma (Python
  Python (programming language)
  Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
  
   library, proprietary)
• Gecode (C++ library, free software: X11 style)
• Google CP Solver (Python
  Python (programming language)
  Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
  
  , Java
  Java (programming language)
  Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
  
  , and C++
  C++
  C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
  
   library, Apache license
  Apache License
  The Apache License is a copyfree free software license authored by the Apache Software Foundation . The Apache License requires preservation of the copyright notice and disclaimer....
  
  )
• IBM
  IBM
  International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
  
   ILOG
  ILOG
  ILOG is an international software company owned by IBM. It creates enterprise software products for supply chain, business rule management, visualization and optimization....
  
   CP (C++ library, proprietary) and CP Optimizer (C++, Java, .NET libraries, proprietary) successor of ILOG Solver, which was considered the market leader in commercial constraint programming software as of 2006
• JaCoP
  JaCoP (solver)
  JaCoP is a constraint solver for constraint satisfaction problems. It is written in Java and it is provided as a Java library. Its main focus is on ease of use, modeling power, as well as efficiency. It has a large collection of global constraints implemented to facilitate problem modeling. JaCoP...
  
   (Java library, open source) available here
• JOpt (Java
  Java (programming language)
  Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
  
   library, free software)
• JSR-331 (Java Constraint Programming API, JCP standard)
• Koalog Constraint Solver (Java library, proprietary)
• Minion
  Minion (solver)
  Minion is a solver for constraint satisfaction problems. Unlike constraint programming toolkits, which expect users to write programs in a traditional programming language like C++, Java or Prolog, Minion takes a text file which specifies the problem, and solves using only this...
  
   (C++ program, GPL)
• python-constraint (Python
  Python (programming language)
  Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
  
   library, GPL)
• Turtle++ (C++
  C++
  C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
  
   library - inspired by the Turtle Language, free software)

Some languages that support constraint programming

• Alma-0
  Alma-0
  Alma-0 is a multi-paradigm computer programming language. This language is an augmented version of the imperative Modula-2 language with logic-programming features and convenient backtracking capability. It is small, strongly typed, and combines constraint programming, a limited number of features...
  
   a small, strongly typed
  Type system
  A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to ensure or prove that no type errors can occur...
  
  , constraint language with a limited number of features inspired by logic programming, supporting imperative programming.
• Bertrand
  Bertrand (programming language)
  Bertrand is a computer programming language for creating constraint programming systems. The language was created by Wm Leler in the mid-1980s as part of his doctoral research...
  
   a language for building constraint programming systems.
• Common Lisp
  Common Lisp
  Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
  
   via Screamer (a free software library which provides backtracking and CLP(R), CHiP features).

See also

• Combinatorial optimization
  Combinatorial optimization
  In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
  
  
• Constraint satisfaction
  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 logic programming
• Heuristic algorithms
• Mathematical programming
  Mathematical Programming
  Mathematical Programming, established in 1971, and published by Springer Science+Business Media, is the official scientific journal of the Mathematical Optimization Society. It currently consists of two series: A and B. The "A" series contains general publications. The "B" series focuses on topical...
  
   (Optimization theory)
• Nurse scheduling problem
  Nurse scheduling problem
  The Nurse scheduling problem is the problem of determining a work schedule for nurses that is both reasonable and efficient. Despite seeming trivial, this is a complex problem due to its many constraints and many possible combinations....
  
  
• Concurrent Constraint Programming (CCP)

External links

• Information on the annual CP conference
• On-Line Guide to Constraint Programming
• Program Does Not Equal Program: Constraint Programming and its Relationship to Mathematical Programming
• Mozart (Oz based, Free software: X11 style)
• Cork Constraint Computation Centre (4C)
• Global Constraint Catalog