Constraint programming (CP)
is a paradigm for solving
combinatorial problems that draws on a wide range of techniques from
artificial intelligence
Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
,
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, and
operations research
Operations research () (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a branch of applied mathematics that deals with the development and application of analytical methods to improve management and ...
. In constraint programming, users declaratively state the
constraints on the feasible solutions for a set of decision variables. Constraints differ from the common
primitives of
imperative programming
In computer science, imperative programming is a programming paradigm of software that uses Statement (computer science), statements that change a program's state (computer science), state. In much the same way that the imperative mood in natural ...
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
backtracking and
constraint propagation, but may use customized code like a problem-specific branching
heuristic.
Constraint programming takes its root from and 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
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declarat ...
,
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.
Constraint logic programming
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
Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving, and computational linguistics.
Prolog has its roots in first-order logic, a formal logic. Unlike many other programming language ...
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.
Constraint satisfaction problem
A constraint is a relation between multiple variables that limits the values these variables can take simultaneously.
Three categories of constraints exist:
* extensional constraints: constraints are defined by enumerating the set of values that would satisfy them;
* arithmetic constraints: constraints are defined by an arithmetic expression, i.e., using
;
* logical constraints: constraints are defined with an explicit semantics, i.e., ''AllDifferent'', ''AtMost'',''...''
Assignment is the association of a variable to a value from its domain. A partial assignment is when a subset of the variables of the problem has been assigned. A total assignment is when all the variables of the problem have been assigned.
During the search of the solutions of a CSP, a user can wish for:
* finding a solution (satisfying all the constraints);
* finding all the solutions of the problem;
*
proving the unsatisfiability of the problem.
Constraint optimization problem
A constraint optimization problem (COP) is a constraint satisfaction problem associated to an objective function.
An ''optimal solution'' to a minimization (maximization) COP is a solution that minimizes (maximizes) the value of the ''objective function''.
During the search of the solutions of a COP, a user can wish for:
* finding a solution (satisfying all the constraints);
* finding the best solution with respect to the objective;
* proving the optimality of the best found solution;
* proving the unsatisfiability of the problem.
Perturbation vs refinement models
Languages for constraint-based programming follow one of two approaches:
* 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 formula evaluation in
spreadsheet
A spreadsheet is a computer application for computation, organization, analysis and storage of data in tabular form. Spreadsheets were developed as computerized analogs of paper accounting worksheets. The program operates on data entered in c ...
s 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.
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
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
domains,
rational domains
*
interval domains, in particular for
scheduling problems
*
linear
In mathematics, the term ''linear'' is used in two distinct senses for two different properties:
* linearity of a '' function'' (or '' mapping'');
* linearity of a '' polynomial''.
An example of a linear function is the function defined by f(x) ...
domains, where only
linear
In mathematics, the term ''linear'' is used in two distinct senses for two different properties:
* linearity of a '' function'' (or '' mapping'');
* linearity of a '' polynomial''.
An example of a linear function is the function defined by f(x) ...
functions are described and analyzed (although approaches to
non-linear problems do exist)
*
finite domains, where constraints are defined over
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
is a finite set with five elements. Th ...
s
* 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 () (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a branch of applied mathematics that deals with the development and application of analytical methods to improve management and ...
) constraint programming is often identified with constraint programming over finite domains.
Constraint propagation
Local consistency conditions are properties of
constraint satisfaction problems related to the
consistency of subsets of variables or constraints. They can be used to reduce the search space and make the problem easier to solve. Various kinds of local consistency conditions are leveraged, including node consistency, arc consistency, and path consistency.
Every local consistency condition can be enforced by a transformation that changes the problem without changing its solutions. Such a transformation is called
constraint propagation.
Constraint propagation works by reducing domains of variables, strengthening constraints, or creating new ones. This leads to a reduction of the search space, making the problem easier to solve by some algorithms. Constraint propagation can also be used as an unsatisfiability checker, incomplete in general but complete in some particular cases.
Constraint solving
There are three main algorithmic techniques for solving constraint satisfaction problems: backtracking search, local search, and dynamic programming.
Backtracking search
Backtracking search is a general
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
for finding all (or some) solutions to some
computational problems, notably
constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.
Local Search
Local search is an incomplete method for finding a solution to a
problem
Problem solving is the process of achieving a goal by overcoming obstacles, a frequent part of most activities. Problems in need of solutions range from simple personal tasks (e.g. how to turn on an appliance) to complex issues in business an ...
. It is based on iteratively improving an assignment of the variables until all constraints are satisfied. In particular, local search algorithms typically modify the value of a variable in an assignment at each step. The new assignment is close to the previous one in the space of assignment, hence the name ''local search''.
Dynamic programming
Dynamic programming is both a
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
method and a computer programming method. It refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a
recursive manner. While some
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
s cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have
optimal substructure.
Example
The syntax for expressing constraints over finite domains depends on the host language. The following is a
Prolog
Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving, and computational linguistics.
Prolog has its roots in first-order logic, a formal logic. Unlike many other programming language ...
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 = ,E,N,D,M,O,R,Y % 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 . 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.
See also
*
Combinatorial optimization
*
Concurrent constraint logic programming
*
Constraint logic programming
*
Heuristic algorithms
*
List of constraint programming languages
*
Mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
*
Nurse scheduling problem
*
Regular constraint
*
Satisfiability modulo theories
*
Traveling tournament problem
References
External links
Association for Constraint ProgrammingCP Conference SeriesGuide to Constraint Programming*, an
Oz-based free software (
X Window System
The X Window System (X11, or simply X) is a windowing system for bitmap displays, common on Unix-like operating systems.
X originated as part of Project Athena at Massachusetts Institute of Technology (MIT) in 1984. The X protocol has been at ...
style)
*
{{Authority control
Programming paradigms
Declarative programming
Articles with example code