Misplaced Pages

#841158

61-454: Examples of problems that can be modeled as a constraint satisfaction problem include: These are often provided with tutorials of CP , ASP, Boolean SAT and SMT solvers. In the general case, constraint problems can be much harder, and may not be expressible in some of these simpler systems. "Real life" examples include automated planning , lexical disambiguation , musicology , product configuration and resource allocation . The existence of

122-414: A set , which may or may not hold. As an example, " is less than " is a relation on the set of natural numbers ; it holds, for instance, between the values 1 and 3 (denoted as 1 < 3 ), and likewise between 3 and 4 (denoted as 3 < 4 ), but not between the values 3 and 1 nor between 4 and 4 , that is, 3 < 1 and 4 < 4 both evaluate to false. As another example, " is sister of "

183-504: A 2-element domain and where all the available relations are Boolean operators . This result has been generalized for various classes of CSPs, most notably for all CSPs over finite domains. This finite-domain dichotomy conjecture was first formulated by Tomás Feder and Moshe Vardi, and finally proven independently by Andrei Bulatov and Dmitriy Zhuk in 2017. Other classes for which a complexity dichotomy has been confirmed are Most classes of CSPs that are known to be tractable are those where

244-415: A Boolean matrix is shown in the middle table; the representation both as a Hasse diagram and as a directed graph is shown in the left picture. The following are equivalent: As another example, define the relation R el on R by The representation of R el as a 2D-plot obtains an ellipse, see right picture. Since R is not finite, neither a directed graph, nor a finite Boolean matrix, nor

305-433: A Hasse diagram can be used to depict R el . Some important properties that a relation R over a set X may have are: The previous 2 alternatives are not exhaustive; e.g., the red relation y = x given in the diagram below is neither irreflexive, nor reflexive, since it contains the pair (0,0) , but not (2,2) , respectively. Again, the previous 3 alternatives are far from being exhaustive; as an example over

366-411: A complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision 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

427-425: A constraint of P {\displaystyle P} such as X i ⊆ X A {\displaystyle {\mathcal {X}}_{i}\subseteq {\mathcal {X_{\mathcal {A}}}}} , the assignment A {\displaystyle {\mathcal {A}}} satisfies the constraint C i {\displaystyle C_{i}} if and only if all

488-503: A constraint satisfaction problem is defined as a triple ⟨ X , D , C ⟩ {\displaystyle \langle X,D,C\rangle } , where Each variable X i {\displaystyle X_{i}} can take on the values in the nonempty domain D i {\displaystyle D_{i}} . Every constraint C j ∈ C {\displaystyle C_{j}\in C}

549-405: A constraint satisfaction problem. More precisely, they are methods that enforce a form of local consistency , which are conditions related to the consistency of a group of variables and/or constraints. Constraint propagation has various uses. First, it turns a problem into one that is equivalent but is usually simpler to solve. Second, it may prove satisfiability or unsatisfiability of problems. This

610-407: A general algorithm 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 is an incomplete method for finding a solution to a problem . It

671-426: A model of static, inflexible constraints. This rigid model is a shortcoming that makes it difficult to represent problems easily. Several modifications of the basic CSP definition have been proposed to adapt the model to a wide variety of problems. Dynamic CSPs ( DCSP s) are useful when the original formulation of a problem is altered in some way, typically because the set of constraints to consider evolves because of

SECTION 10

#1733094066842

732-970: 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 , 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 programming

793-400: 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. There are three main algorithmic techniques for solving constraint satisfaction problems: backtracking search, local search, and dynamic programming. Backtracking search is

854-467: A set of decision variables. 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. 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

915-761: A solution of a problem, but they may fail even if the problem is satisfiable. They work by iteratively improving a complete assignment over the variables. At each step, a small number of variables are changed in value, with the overall aim of increasing the number of constraints satisfied by this assignment. The min-conflicts algorithm is a local search algorithm specific for CSPs and is based on that principle. In practice, local search appears to work well when these changes are also affected by random choices. An integration of search with local search has been developed, leading to hybrid algorithms . CSPs are also studied in computational complexity theory , finite model theory and universal algebra . It turned out that questions about

976-471: A solution to a CSP can be viewed as a decision problem . This can be decided by finding a solution, or failing to find a solution after exhaustive search ( stochastic algorithms typically never reach an exhaustive conclusion, while directed searches often do, on sufficiently small problems). In some cases the CSP might be known to have solutions beforehand, through some other mathematical inference process. Formally,

1037-510: Is consistent if it does not violate any of the constraints. An evaluation is complete if it includes all variables. An evaluation is a solution if it is consistent and complete; such an evaluation is said to solve the constraint satisfaction problem. Constraint satisfaction problems on finite domains are typically solved using a form of search . The most used techniques are variants of backtracking , constraint propagation , and local search . These techniques are also often combined, as in

1098-412: Is a k {\displaystyle k} -ary relation on the corresponding product of domains × i ∈ t j D i {\displaystyle \times _{i\in t_{j}}D_{i}} where the product is taken with indices in ascending order. An evaluation of the variables is a function from a subset of variables to a particular set of values in

1159-423: 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: Languages for constraint-based programming follow one of two approaches: Constraint propagation in constraint satisfaction problems

1220-422: Is a member of R . For example, the relation " is less than " on the natural numbers is an infinite set R less of pairs of natural numbers that contains both (1,3) and (3,4) , but neither (3,1) nor (4,4) . The relation " is a nontrivial divisor of " on the set of one-digit natural numbers is sufficiently small to be shown here: R dv = { (2,4), (2,6), (2,8), (3,6), (3,9), (4,8) } ; for example 2

1281-411: Is a nontrivial divisor of 8 , but not vice versa, hence (2,8) ∈ R dv , but (8,2) ∉ R dv . If R is a relation that holds for x and y one often writes xRy . For most common relations in mathematics, special symbols are introduced, like " < " for "is less than" , and " | " for "is a nontrivial divisor of" , and, most popular " = " for "is equal to" . For example, " 1 < 3 ", " 1

SECTION 20

#1733094066842

1342-400: Is a relation on the set of all people, it holds e.g. between Marie Curie and Bronisława Dłuska , and likewise vice versa. Set members may not be in relation "to a certain degree" – either they are in relation or they are not. Formally, a relation R over a set X can be seen as a set of ordered pairs ( x , y ) of members of X . The relation R holds between x and y if ( x , y )

1403-572: Is a typical example of a refinement model, and formula evaluation in 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. The constraints used in constraint programming are typically over some specific domains. Some popular domains for constraint programming are: Finite domains

1464-402: Is an element of " on the class of all sets, see Binary relation § Sets versus classes ). Given a set X , a relation R over X is a set of ordered pairs of elements from X , formally: R ⊆ { ( x , y ) | x , y ∈ X } . The statement ( x , y ) ∈ R reads " x is R -related to y " and is written in infix notation as xRy . The order of the elements

1525-399: 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

1586-448: 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 is both a mathematical optimization method and a computer programming method. It refers to simplifying

1647-400: Is checked; in case of consistency, a recursive call is performed. When all values have been tried, the algorithm backtracks. In this basic backtracking algorithm, consistency is defined as the satisfaction of all constraints whose variables are all assigned. Several variants of backtracking exist. Backmarking improves the efficiency of checking consistency. Backjumping allows saving part of

1708-504: Is defined by a triplet ( X , D , C ) {\displaystyle ({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})} where: Three categories of constraints exist: Definition  —  An assignment (or model) A {\displaystyle {\mathcal {A}}} of a CSP P = ( X , D , C ) {\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}

1769-422: Is defined by the couple A = ( X A , V A ) {\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})} where: 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

1830-554: Is equationally non-trivial, and NP-hard otherwise. The complexity of such infinite-domain CSPs as well as of other generalisations (Valued CSPs, Quantified CSPs, Promise CSPs) is still an area of active research. [1] [2] Every CSP can also be considered as a conjunctive query containment problem. A similar situation exists between the functional classes FP and #P . By a generalization of Ladner's theorem , there are also problems in neither FP nor #P-complete as long as FP ≠ #P. As in

1891-571: Is important; if x ≠ y then yRx can be true or false independently of xRy . For example, 3 divides 9 , but 9 does not divide 3 . A relation R on a finite set X may be represented as: A transitive relation R on a finite set X may be also represented as For example, on the set of all divisors of 12 , define the relation R div by Formally, X = { 1, 2, 3, 4, 6, 12 } and R div = { (1,2), (1,3), (1,4), (1,6), (1,12), (2,4), (2,6), (2,12), (3,6), (3,12), (4,12), (6,12) } . The representation of R div as

Constraint satisfaction problem - Misplaced Pages Continue

1952-439: Is in turn a pair ⟨ t j , R j ⟩ {\displaystyle \langle t_{j},R_{j}\rangle } , where t j ⊆ { 1 , 2 , … , n } {\displaystyle t_{j}\subseteq \{1,2,\ldots ,n\}} is a set of k {\displaystyle k} indices and R j {\displaystyle R_{j}}

2013-533: Is irreflexive if, and only if, it is asymmetric". Of particular importance are relations that satisfy certain combinations of properties. A partial order is a relation that is reflexive, antisymmetric, and transitive, an equivalence relation is a relation that is reflexive, symmetric, and transitive, a function is a relation that is right-unique and left-total (see below ). Since relations are sets, they can be manipulated using set operations, including union , intersection , and complementation , leading to

2074-456: Is less than 3 ", and " (1,3) ∈ R less " mean all the same; some authors also write " (1,3) ∈ (<) ". Various properties of relations are investigated. A relation R is reflexive if xRx holds for all x , and irreflexive if xRx holds for no x . It is symmetric if xRy always implies yRx , and asymmetric if xRy implies that yRx is impossible. It is transitive if xRy and yRz always implies xRz . For example, "

2135-507: Is less than " is irreflexive, asymmetric, and transitive, but neither reflexive nor symmetric. " is sister of " is transitive, but neither reflexive (e.g. Pierre Curie is not a sister of himself), nor symmetric, nor asymmetric; while being irreflexive or not may be a matter of definition (is every woman a sister of herself?), " is ancestor of " is transitive, while " is parent of " is not. Mathematical theorems are known about combinations of relation properties, such as "a transitive relation

2196-499: Is not guaranteed to happen in general; however, it always happens for some forms of constraint propagation and/or for certain kinds of problems. The most known and used forms of local consistency are arc consistency , hyper-arc consistency , and path consistency . The most popular constraint propagation method is the AC-3 algorithm , which enforces arc consistency. Local search methods are incomplete satisfiability algorithms. They may find

2257-407: 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. 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

2318-399: Is said to be contained in a relation S over X and Y , written R ⊆ S , if R is a subset of S , that is, for all x ∈ X and y ∈ Y , if xRy , then xSy . If R is contained in S and S is contained in R , then R and S are called equal written R = S . If R is contained in S but S is not contained in R , then R

2379-454: Is said to be smaller than S , written R ⊊ S . For example, on the rational numbers , the relation > is smaller than ≥ , and equal to the composition > ∘ > . The above concept of relation has been generalized to admit relations between members of two different sets. Given sets X and Y , a heterogeneous relation R over X and Y is a subset of { ( x , y ) | x ∈ X , y ∈ Y } . When X = Y ,

2440-424: Is said to have optimal substructure . 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: 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

2501-681: Is when all the variables of the problem have been assigned. Property  —  Given A = ( X A , V A ) {\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})} an assignment (partial or total) of a CSP P = ( X , D , C ) {\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})} , and C i = ( X i , R i ) {\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}

Constraint satisfaction problem - Misplaced Pages Continue

2562-446: The VLNS method, and current research involves other technologies such as linear programming . Backtracking is a recursive algorithm. It maintains a partial assignment of the variables. Initially, all variables are unassigned. At each step, a variable is chosen, and all possible values are assigned to it in turn. For each value, the consistency of the partial assignment with the constraints

2623-523: The algebra of sets . Furthermore, the calculus of relations includes the operations of taking the converse and composing relations . The above concept of relation has been generalized to admit relations between members of two different sets ( heterogeneous relation , like " lies on " between the set of all points and that of all lines in geometry), relations between three or more sets ( finitary relation , like "person x lives in town y at time z " ), and relations between classes (like "

2684-411: The hypergraph of constraints has bounded treewidth , or where the constraints have arbitrary form but there exist equationally non-trivial polymorphisms of the set of constraint relations. An infinite-domain dichotomy conjecture has been formulated for all CSPs of reducts of finitely bounded homogenous structures, stating that the CSP of such a structure is in P if and only if its polymorphism clone

2745-421: The complexity of CSPs translate into important universal-algebraic questions about underlying algebras. This approach is known as the algebraic approach to CSPs. Since every computational decision problem is polynomial-time equivalent to a CSP with an infinite template, general CSPs can have arbitrary complexity. In particular, there are also CSPs within the class of NP-intermediate problems, whose existence

2806-413: The constraint C i {\displaystyle C_{i}} belongs to R i {\displaystyle {\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: A constraint optimization problem (COP)

2867-457: The corresponding subset of domains. An evaluation v {\displaystyle v} satisfies a constraint ⟨ t j , R j ⟩ {\displaystyle \langle t_{j},R_{j}\rangle } if the values assigned to the variables t j {\displaystyle t_{j}} satisfy the relation R j {\displaystyle R_{j}} . An evaluation

2928-528: The decision case, a problem in the #CSP is defined by a set of relations. Each problem takes a Boolean formula as input and the task is to compute the number of satisfying assignments. This can be further generalized by using larger domain sizes and attaching a weight to each satisfying assignment and computing the sum of these weights. It is known that any complex weighted #CSP problem is either in FP or #P-hard. The classic model of Constraint Satisfaction Problem defines

2989-413: 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

3050-528: The environment. DCSPs are viewed as a sequence of static CSPs, each one a transformation of the previous one in which variables and constraints can be added (restriction) or removed (relaxation). Information found in the initial formulations of the problem can be used to refine the next ones. The solving method can be classified according to the way in which information is transferred: Classic CSPs treat constraints as hard, meaning that they are imperative (each solution must satisfy all of them) and inflexible (in

3111-497: The natural numbers, the relation xRy defined by x > 2 is neither symmetric (e.g. 5 R 1 , but not 1 R 5 ) nor antisymmetric (e.g. 6 R 4 , but also 4 R 6 ), let alone asymmetric. Uniqueness properties: Totality properties: Relations that satisfy certain combinations of the above properties are particularly useful, and thus have received names by their own. Orderings: Uniqueness properties: Uniqueness and totality properties: A relation R over sets X and Y

SECTION 50

#1733094066842

3172-413: 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. Relation (mathematics) In mathematics , a relation denotes some kind of relationship between two objects in

3233-478: 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

3294-444: The search by backtracking "more than one variable" in some cases. Constraint learning infers and saves new constraints that can be later used to avoid part of the search. Look-ahead is also often used in backtracking to attempt to foresee the effects of choosing a variable or a value, thus sometimes determining in advance when a subproblem is satisfiable or unsatisfiable. Constraint propagation techniques are methods used to modify

3355-499: The sense that they must be completely satisfied or else they are completely violated). Flexible CSP s relax those assumptions, partially relaxing the constraints and allowing the solution to not comply with all of them. This is similar to preferences in preference-based planning . Some types of flexible CSPs include: In DCSPs each constraint variable is thought of as having a separate geographic location. Strong constraints are placed on information exchange between variables, requiring

3416-418: 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

3477-403: 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

3538-423: The use of fully distributed algorithms to solve the constraint satisfaction problem. Constraint programming Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence , computer science , and operations research . In constraint programming, users declaratively state the constraints on the feasible solutions for

3599-404: The values V A i = { v i ∈ V A  tel que  x i ∈ X i } {\displaystyle {\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}} of the variables of

3660-521: 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. 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)

3721-433: Was demonstrated by Ladner , under the assumption that P ≠ NP . However, a large class of CSPs arising from natural applications satisfy a complexity dichotomy, meaning that every CSP within that class is either in P or NP-complete . These CSPs thus provide one of the largest known subsets of NP which avoids NP-intermediate problems. A complexity dichotomy was first proven by Schaefer for Boolean CSPs, i.e. CSPs over

SECTION 60

#1733094066842
#841158