Decomposition Methods
Decomposition methods create a problem that is easy to solve from an arbitrary one. Each variable of this new problem is associated to a set of original variables; its domain contains tuples of values for the variables in the associated set; in particular, these are the tuples that satisfy a set of constraints over these variables. The constraints of the new problem bounds the values of two new variables to have as values two tuples that agree on the shared original variables. Three further conditions ensure that the new problem is equivalent to the old one and can be solved efficiently.
In order for the new problem to be solvable efficiently, the primal graph of the new problem is required to be acyclic. In other words, viewing the variables as vertices and the (binary) constraints as edges, the resulting graph is required to be a tree or a forest.
In order for the new problem to be equivalent to the old one, each original constraint is enforced as part of the definition of the domain of at least one new variables. This requires that, for each constraint of the old problem, there exists a variable of the new problem such that its associated set of original variables include the scope of the constraint, and all tuples in its domain satisfy the constraint.
A further condition that is necessary to ensure equivalence is that the binary constraints are sufficient to enforce all "copies" of each original variable to assume the same value. Since the same original variable can be associated to several of the new variables, the values of these new variable must all agree on the value of the old variable. The binary constraints are used to enforce equality of the old variables shared between the two new variables. Two copies of a new variable are forced equal if there exists a path of binary constraints between their new variables and all new variables in this path contain the old variable.
| An example constraint satisfaction problem; this problem is binary, and the constraints are represented by edges of this graph. | |
| A decomposition tree; for every edge of the original graph, there is a node that contains both its endpoints; all nodes containing a variable are connected | |
| Solving a subproblem. This example shows solving the subproblem made of all constraints on the variables of the first set . A similar procedure is done for the other sets and | |
| Each node of the tree is made a variable. Its domain is the set of solutions of the partial problem, which is a set of tuples. The constraints of the new problem allow only the tuples that contain equal values of the original variables. In the figure, equality of is shown: the corresponding constraint is only met by the first tuple of and the first tuple of, and by the second tuple of and the second tuple of . |
A decomposition method is usually defined by providing a tree whose nodes are the variables of the new problem; for each node, also provided are the associated set of original variables and possibly a set of original constraints used to build the domain of the variable in the new problem. Of the above three conditions (tree structure, enforcement of constraints, and equivalence of copies of original variables), the first one is automatically enforced by this definition. The condition of enforcement of constraints is in mostly formulated as: the scope of each constraint is a subset of the variables of some node; however, a different condition may be used when nodes are also associated to sets of constraints. The equivalence of all copies of the original variables is usually formulated as: the subgraph induced by the nodes associated to an original variable is connected.
Read more about this topic: Decomposition Method (constraint Satisfaction)
Famous quotes containing the word methods:
“The reading public is intellectually adolescent at best, and it is obvious that what is called “significant literature” will only be sold to this public by exactly the same methods as are used to sell it toothpaste, cathartics and automobiles.”
—Raymond Chandler (1888–1959)