Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Constraint programming
open-in-new
<p>Constraint programming (CP) is a paradigm for solving <a href="/facts/Combinatorial/k14xUoKT">combinatorial</a> problems that draws on a wide range of techniques from <a href="/facts/Artificial_intelligence/lJGauQwX">artificial intelligence</a>, <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, and <a href="/facts/Operations_research/H5yJkV5n">operations research</a>. In constraint programming, users declaratively state the <a href="/facts/Constraint_(mathematics)/QLFIFlFX">constraints</a> on the feasible solutions for a set of decision variables. Constraints differ from the common <a href="/facts/Language_primitive/S6V6qfVS">primitives</a> of <a href="/facts/Imperative_programming/6b5dUnE1">imperative programming</a> 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. In addition to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronological <a href="/facts/Backtracking/Jm9vDUk8">backtracking</a> and <a href="/facts/Constraint_propagation/wqM9hKc1">constraint propagation</a>, but may use customized code like a problem-specific branching <a href="/facts/Heuristic_(computer_science)/PM2qkoa2">heuristic</a>. </p><p>Constraint programming takes its root from and can be expressed in the form of <a href="/facts/Constraint_logic_programming/b47VLwE9">constraint logic programming</a>, which embeds constraints into a <a href="/facts/Logic_program/Xgh8lj3F">logic program</a>. This variant of logic programming is due to Jaffar and Lassez, who extended in 1987 a specific class of constraints that were introduced in <a href="/facts/Prolog_II/r5h66Qh1">Prolog II</a>. The first implementations of constraint logic programming were Prolog III, <a href="/facts/CLP(R)/DUyNvoaJ">CLP(R)</a>, and <a href="/facts/CHIP_(programming_language)/7DVD4pxn">CHIP</a>. </p><p>Instead of logic programming, constraints can be mixed with <a href="/facts/Functional_programming/cdxqPEIM">functional programming</a>, <a href="/facts/Term_rewriting/9PHlnnnJ">term rewriting</a>, and <a href="/facts/Imperative_language/6b5dUnE1">imperative languages</a>. Programming languages with built-in support for constraints include <a href="/facts/Oz_programming_language/Fsb7wHsv">Oz</a> (functional programming) and <a href="/facts/Kaleidoscope_programming_language/LQnNkCXz">Kaleidoscope</a> (imperative programming). Mostly, constraints are implemented in imperative languages via <i>constraint solving toolkits</i>, which are separate libraries for an existing imperative language. </p>