Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 22:12, 11 May 2013

Revision as of 13:12, 18 December 2013

Line 15:

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 constraint graph]]{{dn|date=Aprilprimal 2013}}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 (graph theory)|tree]] or a [[Forest (graph theory)|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.