# Constraint programming

This article possibly contains original research. (June 2011) (Learn how and when to remove this template message) |

In computer science, **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*), linear inequalities (e.g., `x` ≤ 5), and others. Constraints are usually embedded within a programming language or provided via separate software libraries.

Constraint programming can be expressed in the form of 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.

Instead of logic programming, constraints can be mixed with functional programming, term rewriting, and imperative languages.
Programming languages with built-in 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[edit]

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

## Perturbation vs refinement models[edit]

Languages for constraint-based programming follow one of two approaches:^{[1]}

- Refinement model: variables in the problem are initially unassigned, and each variable is assumed to be able to contain any value included in its range or domain. As computation progresses, values in the domain of a variable are pruned if they are shown to be incompatible with the possible values of other variables, until a single value is found for each variable.
- Perturbation model: variables in the problem are assigned a single initial value. At different times one or more variables receive perturbations (changes to their old value), and the system propagates the change trying to assign new values to other variables that are consistent with the perturbation.

Constraint propagation in constraint satisfaction problems is a typical example of a refinement model, and spreadsheets are a typical example of a perturbation model.

The refinement model is more general, as it does not restrict variables to have a single value, it can lead to several solutions to the same problem. However, the perturbation model is more intuitive for programmers using mixed imperative constraint object-oriented languages.^{[2]}

## Domains[edit]

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
- interval domains, in particular for scheduling problems
- linear domains, where only linear 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) 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:

```
% This code works in both YAP and SWI-Prolog using the environment-supplied
% CLPFD constraint solver library. It may require minor modifications to work
% in other Prolog environments or using other constraint solvers.
:- use_module(library(clpfd)).
sendmore(Digits) :-
Digits = [S,E,N,D,M,O,R,E], % Create variables
Digits ins 0..9, % Associate domains to variables
S #\= 0, % Constraint: S must be different from 0
M #\= 0,
all_different(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,
label(Digits). % Start the search
```

The interpreter creates a variable for each letter in the puzzle. The operator `ins`

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 `all_different(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 `all_different`

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 **label** literals are used to actually perform search for a solution.

## Constraint programming libraries for general-purpose programming languages[edit]

Constraint programming is often realized in imperative programming via a separate library. Some popular libraries for constraint programming are:

- Artelys Kalis, C++, Java, Python library, FICO Xpress module (proprietary)
- Cassowary, Smalltalk, C++, Java, Python, JavaScript, Ruby library (LGPL)
- CHIP V5, C++ and C libraries (proprietary)
- Choco, Java library (BSD license)
- Comet, C style language for constraint programming, constraint-based local search and mathematical programming (free binaries available for academic use)
- Cream, Java library (LGPL)
- Disolver, C++ library (proprietary)
- Facile, OCaml library (CC0 1.0)
- finite-domain, Haskell library (MIT)
- Gecode, C++ library, Python bindings (X11-style free software)
- Google OR-Tools, C++, Python, Java, .NET library (Apache License 2.0)
- IBM ILOG CP Optimizer: C++, Python, Java, .NET libraries (proprietary, free for academic use).
^{[3]}Successor of ILOG Solver/Scheduler, which was considered the market leader in commercial constraint programming software as of 2006^{[4]} - JaCoP, Java library (open source)
- JOpt, Java library (free software)
- JSR-331, Java constraint programming API, JCP standard
- Koalog Constraint Solver, Java library (proprietary)
- LINDO (proprietary)
- MonadicCP, Haskell library (BSD-3-Clause)
- Numberjack, Python platform (LGPL)
- Minion, C++ program (GPL)
- python-constraint, Python library (GPL)
- OscaR, Scala library (LGPL)
- Scarab, Scala library (BSD license)
- SMOCS, Scala Monadic library (BSD license)
- OptaPlanner, Java library (that also works in Kotlin, Scala, JRuby and Groovy) and toolkit (benchmarker, server and workbench) (Apache license)
- Z3, C++ solver with C, Java, C#, and Python bindings (MIT license)

## Some languages that support constraint programming[edit]

- AIMMS, an algebraic modeling language with support for constraint programming.
^{[5]} - Alma-0, a small, strongly typed, constraint language with a limited number of features inspired by logic programming, supporting imperative programming.
- AMPL, an algebraic modeling language with support for constraint programming.
^{[6]} - Babelsberg, a family of object-constraint programming languages for Ruby, JavaScript, Squeak, and Python.
^{[7]} - Bertrand, a language for building constraint programming systems.
- Common Lisp via Screamer, a free software library which provides backtracking and CLP(R), CHiP features.
- Constraint Handling Rules
- MiniZinc, a high-level constraint programming system (BSD-style license)
- Kaleidoscope, an object-oriented imperative constraint programming language.
- Oz
- Claire
- Curry, Haskell-based language with free implementations.
- The SystemVerilog computer hardware simulation language has a built in constraint solver.
- Wolfram Language
- XCSP3, an XML-based intermediate integrated format that can represent each instance separately while preserving its structure. (BSD-style license)

### Logic programming based constraint logic languages[edit]

- B-Prolog, Prolog-based (proprietary)
- CHIP V5,
^{[8]}Prolog-based, also includes C++ and C libraries (proprietary) - Ciao, Prolog-based (GPL/LGPL)
- ECLiPSe, Prolog-based (open source)
- miniKanren
^{[9]}, Scheme-based (open source) - SICStus, Prolog-based (proprietary)
- GNU Prolog (free software)
- Picat (open C source)
- YAP (Prolog)
- SWI-Prolog, a free Prolog system containing several libraries for constraint solving
- Jekejeke Logic Programming, Prolog-based (proprietary)
- F1 Compiler, a no-cost software (proprietary)

## See also[edit]

- Combinatorial optimization
- Constraint logic programming
- Concurrent constraint logic programming
- Mathematical optimization
- Heuristic algorithms
- Nurse scheduling problem
- Traveling tournament problem

## References[edit]

**^**Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (1993).*Constraint Programming*. Springer Science+Business Media. p. 76. ISBN 9783642859830.**^**Lopez, G., Freeman-Benson, B., & Borning, A. (1994, January). Kaleidoscope: A constraint imperative programming language. In*Constraint Programming*(pp. 313-329). Springer Berlin Heidelberg.**^**Laborie P, Rogerie J, Shaw P, Vilim P (2018). "IBM ILOG CP optimizer for scheduling".*Constraints*.**23**(2): 210–250. doi:10.1007/s10601-018-9281-x.**^**Francesca Rossi; Peter Van Beek; Toby Walsh (2006).*Handbook of constraint programming*. Elsevier. p. 157. ISBN 978-0-444-52726-4.**^**van Hoeve, Willem-Jan; Hunting, Marcel; Kuip, Chris (2012). "The AIMMS Interface to Constraint Programming" (PDF).*AIMMS*.**^**Robert Fourer; David M. Gay (2002). "Extending an Algebraic Modeling Language to Support Constraint Programming".*INFORMS Journal on Computing*.**14**(4): 322–344. CiteSeerX 10.1.1.8.9699. doi:10.1287/ijoc.14.4.322.2825.**^**Tim Felgentreff; Alan Borning; Robert Hirschfeld (2014). "Specifying and Solving Constraints on Object Behavior".*Journal of Object Technology*.**13**(4): 1–38. doi:10.5381/jot.2014.13.4.a1.**^**CHIP V5*COSYTEC***^**Press, The MIT. "The Reasoned Schemer, Second Edition".*The MIT Press*. Retrieved 2019-02-19.

## External links[edit]

Wikimedia Commons has media related to .Constraint programming |

- Association for Constraint Programming
- CP Conference Series
- Guide to Constraint Programming
- The Mozart Programming System at Archive.today (archived December 5, 2012), an Oz-based free software (X11-style)
- Cork Constraint Computation Centre at Archive.today (archived January 7, 2013)
- Global Constraint Catalog