Hybrid Algorithm (constraint Satisfaction) - Tree Decomposition Hybrid Algorithm

Tree Decomposition Hybrid Algorithm

Another hybrid search/inference algorithm works on the tree decomposition. In general, a constraint satisfaction problem can be solved by first creating a tree decomposition and then using a specialized algorithm.

One such algorithm is based on first propagating constraints among nodes, and then solving the subproblem in each node. This propagation consists in creating new constraints that represent the effects of the constraints in a node over a joined node. More precisely, if two nodes are joined, they share variables. The allowed evaluations of these variables according to the constraints of the first node tell how the first node affects the variables of the second node. The algorithm works by creating the constraint satisfied by these evaluations and incorporating this new constraint in the second node.

When all constraints have been propagated from the leaves to the root and back to the root, all nodes contain all constraints that are relevant to them. The problem can therefore be solved in each node.

A hybrid approach can be taken by using variable elimination for creating the new constraints that are propagated within nodes, and a search algorithm (such as backtracking, backjumping, local search) on each individual node.