Movatterモバイル変換

[0]ホーム

Jump to content

Constraint programming

Edit links

From Wikipedia, the free encyclopedia

Programming paradigm wherein relations between variables are stated in the form of constraints

This articlepossibly containsoriginal research. Pleaseimprove it byverifying the claims made and addinginline citations. Statements consisting only of original research should be removed.(June 2011) (Learn how and when to remove this message)

Constraint programming (CP)^[1] is a paradigm for solvingcombinatorial problems that draws on a wide range of techniques fromartificial intelligence,computer science, andoperations research. In constraint programming, users declaratively state theconstraints on the feasible solutions for a set of decision variables. Constraints differ from the commonprimitives ofimperative 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. In addition to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronologicalbacktracking andconstraint propagation, but may use customized code like a problem-specific branchingheuristic.

Constraint programming takes its root from and can be expressed in the form ofconstraint logic programming, which embeds constraints into alogic program. This variant of logic programming is due to Jaffar and Lassez,^[2] who extended in 1987 a specific class of constraints that were introduced inProlog II. The first implementations of constraint logic programming wereProlog III,CLP(R), andCHIP.

Instead of logic programming, constraints can be mixed withfunctional programming,term rewriting, andimperative languages.Programming languages with built-in support for constraints includeOz (functional programming) andKaleidoscope (imperative programming). Mostly, constraints are implemented in imperative languages viaconstraint solving toolkits, which are separate libraries for an existing imperative language.

Constraint logic programming

[edit]

Main article:Constraint logic programming

Constraint programming is an embedding of constraints in a host language. The first host languages used werelogic programming languages, so the field was initially calledconstraint logic programming. The two paradigms share many important features, like logical variables andbacktracking. Today mostProlog 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

[edit]

Main article:Constraint satisfaction problem

A constraint is a relation between multiple variables that limits the values these variables can take simultaneously.

Definition—A constraint satisfaction problem on finite domains (or CSP) is defined by a triplet $({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ where:

${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ is the set of variables of the problem;
${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ is the set of domains of the variables, i.e., for all $k\in [1;n]$ we have $x_{k}\in {\mathcal {D}}_{k}$ ;
${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ is a set of constraints. A constraint $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ is defined by a set ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ of variables and a relation ${\mathcal {R}}_{i}\subseteq {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}$ that defines the set of values allowed simultaneously for the variables of ${\mathcal {X}}_{i}$ .

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 $<,>,\leq ,\geq ,=,\neq ,...$ ;
logical constraints: constraints are defined with an explicit semantics, i.e.,AllDifferent,AtMost,...

Definition— An assignment (or model) ${\mathcal {A}}$ of a CSP $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ is defined by the couple ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ where:

${\mathcal {X_{\mathcal {A}}}}\subseteq {\mathcal {X}}$ is a subset of variable;
${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ is the tuple of the values taken by the assigned variables.

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.

Property—Given ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ an assignment (partial or total) of a CSP $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ , and $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ a constraint of $P {\displaystyle P}$ such as ${\mathcal {X}}_{i}\subseteq {\mathcal {X_{\mathcal {A}}}}$ , the assignment ${\mathcal {A}}$ satisfies the constraint $C_{i}$ if and only if all the values ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ such that }}x_{i}\in {\mathcal {X}}_{i}\}$ of the variables of the constraint $C_{i}$ belongs to ${\mathcal {R}}_{i}$ .

Definition—A solution of a CSP is a total assignment that satisfies all the constraints of the problem.

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

[edit]

Main article:Constrained optimization

A constraint optimization problem (COP) is a constraint satisfaction problem associated to an objective function.

Anoptimal solution to a minimization (maximization) COP is a solution that minimizes (maximizes) the value of theobjective 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

[edit]

Languages for constraint-based programming follow one of two approaches:^[3]

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 inconstraint satisfaction problems is a typical example of a refinement model, and formula evaluation inspreadsheets 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.^[4]

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 forscheduling problems^[5]
linear domains, where onlylinear functions are described and analyzed (although approaches tonon-linear problems do exist)
finite domains, where constraints are defined overfinite 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 (likeoperations research) constraint programming is often identified with constraint programming over finite domains.

Constraint propagation

[edit]

Main article:Constraint propagation

Local consistency conditions are properties ofconstraint satisfaction problems related to theconsistency 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, includingnode consistency,arc consistency, andpath consistency.

Every local consistency condition can be enforced by a transformation that changes the problem without changing its solutions. Such a transformation is calledconstraint propagation.^[6] 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

[edit]

There are three main algorithmic techniques for solving constraint satisfaction problems: backtracking search, local search, and dynamic programming.^[1]

Backtracking search

[edit]

Main article:Backtracking

Backtracking search is a generalalgorithm for finding all (or some) solutions to somecomputational problems, notablyconstraint 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

[edit]

Main article:Local search (constraint satisfaction)

Local search is an incomplete method for finding a solution to aproblem. 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 namelocal search.

Dynamic programming

[edit]

Main article:Dynamic programming

Dynamic programming is both amathematical optimization method and a computer programming method. It refers to simplifying a complicated problem by breaking it down into simpler sub-problems in arecursive manner. While somedecision problems 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 haveoptimal substructure.

Example

[edit]

The syntax for expressing constraints over finite domains depends on the host language. The following is aProlog program that solves the classicalalphametic 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,Y],% Create variablesDigitsins0..9,% Associate domains to variablesS#\=0,% Constraint: S must be different from 0M#\=0,all_different(Digits),% all the elements must take different values1000*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 operatorins 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 constraintall_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 theall_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. Thelabel literals are used to actually perform search for a solution.

References

[edit]

^^a ^bRossi, Francesca; Beek, Peter van;Walsh, Toby (2006).Handbook of Constraint Programming. Elsevier.ISBN 978-0-08-046380-3.
^Jaffar, Joxan; Lassez, J-L. (1987)."Constraint logic programming".POPL87: Fourteenth AnnualACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Association for Computing Machinery. pp. 111–9.doi:10.1145/41625.41635.ISBN 978-0-89791-215-0.
^Borning, A.; Freeman-Benson, B.; Wilson, M. (1993)."Constraint Hierarchies". In Mayoh, B.; Tyugu, E.; Penjam, J. (eds.).Constraint Programming. NATO ASI F. Vol. 131. Springer. p. 76.doi:10.1007/978-3-642-85983-0_4.ISBN 978-3-642-85983-0.
^Lopez, G.; Freeman-Benson, B.; Borning, A. (1993)."Kaleidoscope: A constraint imperative programming language"(PDF). In Mayoh, B.; Tyugu, E.; Penjam, J. (eds.).Constraint Programming. NATO ASI F. Vol. 131. Springer. pp. 313–329.doi:10.1007/978-3-642-85983-0_12.ISBN 978-3-642-85983-0.
^Baptiste, Philippe; Pape, Claude Le; Nuijten, Wim (2012).Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Springer.ISBN 978-1-4615-1479-4.
^Bessiere, Christian (2006). "Constraint Propagation".Handbook of Constraint Programming. Foundations of Artificial Intelligence. Vol. 2. Elsevier. pp. 29–83.CiteSeerX 10.1.1.398.4070.doi:10.1016/s1574-6526(06)80007-6.ISBN 9780444527264.

External links

[edit]

Wikimedia Commons has media related toConstraint programming.

International Conference on Principles and Practice of Constraint Programming.Association for Constraint Programming.
Barták, Roman (1998)."On-line Guide to Constraint Programming". Charles University, Prague.
The Mozart Programming System atarchive.today (archived December 5, 2012), anOz-based free software (X Window System style)
Cork Constraint Computation Centre atarchive.today (archived January 7, 2013)
Shirriff, Ken (October 2025)."Solving the NYTimes Pips puzzle with a constraint solver".
Scassellati, Brian (2019)."Constraint Satisfaction Problems"(PDF).CPSC 470 – Artificial Intelligence. Yale University.

Programming paradigms (Comparison by language)

Imperative

Structured	Jackson structures Block-structured Modular Non-structured Procedural Programming in the large and in the small Design by contract Invariant-based Nested function
Object-oriented (comparison,list)	Class-based,Prototype-based,Object-based Agent Immutable object Persistent Uniform function call syntax

Declarative

Functional (comparison)	Recursive Anonymous function (Partial application) Higher-order Purely functional Total Strict GADTs Dependent types Functional logic Point-free style Expression-oriented Applicative,Concatenative Function-level,Value-level Monad
Dataflow	Flow-based Reactive (Functional reactive) Signals Streams Synchronous
Logic	Abductive logic Answer set Constraint (Constraint logic) Inductive logic Nondeterministic Ontology Probabilistic logic Query
Domain- specific language (DSL)	Algebraic modeling Array Automata-based (Action) Command (Spacecraft) Differentiable End-user Grammar-oriented Interface description Language-oriented List comprehension Low-code Modeling Natural language Non-English-based Page description Pipes andfilters Probabilistic Quantum Scientific Scripting Set-theoretic Simulation Stack-based System Tactile Templating Transformation (Graph rewriting,Production,Pattern) Visual