Transcript Document

Cut-and-Traverse: A new Structural Decomposition Method for CSPs
Yaling Zheng and Berthe Y. Choueiry
Constraint Systems Laboratory • Computer Science & Engineering • University of Nebraska-Lincoln • yzheng, [email protected]
Tree-Structured Decompositions
General principal
1. Decompose a CSP into sub-problems connected in a tree structure
• Compute a constraint tree T equivalent to the hypergraph of the CSP
• Each node in T contains one or more constraints of original CSP
2. Solve each sub-problem (all solutions), usually by a join operation.
3. Apply directional arc-consistency to the constraint tree T.
4. Find a solution for the CSP using backtrack-free search.
Goal: a decomposition technique that is efficient and minimizes width of tree
Cut decomposition: A restricted hinge+ decomposition. During the process of
decomposition, every sub constraint hypergraph contains at least 2 cuts.
s2
s1 s2 s3
s4
s2
s5
Contribution in Context
Hypertree
Traverse Cut-and-Traverse
Cut
Hinge+
Hinge [4]
[7]
Hinge
Biconnected Component
+
+ Hinge
Tree Clustering [4]
+ Hypertree [10]
Tree Clustering
 Treewidth [6]
s4
s
s
5
6 s
s4
s11 6
s5 s s12
12
s11
s11 s17
Constraint Hypergraph
s
9
s
s5
s6 s7
s2 s3
8
s10
1 4 5 6 7 8 9 10 19
s
1 0 2
s17 22
A constraint hypergraph Hcg .
18 20 s16
3 11 12 13 14 15 16 17 21 s15
s4 s11 s12 s13 s14
Given a constraint hypergraph H = (V, E) where H is connected and |E| ≥ k+1. We
call a k-cut of H a set F of hyperedges that satisfies the following conditions:
1. F is a subset of E and |F| = k, and
2. The remaining constraint hypergraph H1, …, Hq has at least 2 components.
Hinge+ Decomposition
 Hinge decomposition continuously finds 1cut in in Hcg
 Width of the 1-hinge tree to the right is 12.
s2 s3 s11 s11s17
s4 s5 s s9
6
s9 s10
s7 s8 s9 s9
s9 s15
s11 s12
s13 s14 s9
s9 s16
Applying hinge decomposition to Hcg.
Hinge+ decomposition of Hcg
 After finding all the 1-cuts, we continuously find 2-cuts in Hcg.
 When there are multiple 2-cuts, we choose the one that yields the best division (i.e.,
the size of the largest sub-problem is the smallest).
 Width of the 2-hinge+ tree below is 5.
s2
s1 s2 s3
s4
s2
s5
s4
s
s
5
6 s
s4
s11 6
s5 s s12
12
s11
s11 s17
9 16
s6
s7 s7
s12 s13
s13
s7
s8 s8
s13 s14
s14
s
s
s9 9 10
s8
s9 s9 s9 s15
s14 s9
s9 s16
This constraint tree is not
a cut decomposition because
the node {s4, s5, s6, s11, s12}
contains 3 cuts:
{s4, s5}, {s6, s12}, and {s11}.
Applying
cut decomposition to Hcg.
Cut-and-Traverse decomposition has the following steps:
1. Decompose the constraint hypergraph using cut decomposition.
The cut decomposition results in a constraint tree T.
2. For each tree node T, traverse it.

If the tree node does not contain any cut, then traverse it from an arbitrary
hyperedge.

If the tree node contains one cut C1, then traverse it from C1.

If the tree node contains two cuts C1 and C2, then traverse it from C1 to C2.
3. Combine the traverse results.
s1 s2
s3
s4
s5 s6 s7
s11 s12 s13
s17
s10
s8 s
9
s15
s14
s16
A Cut-and-Traverse
decomposition of Hcg.
Cut limit size is 2.
Width of the join tree is 2.
Conclusions
1. Hinge+ decomposition: An improvement to hinge decomposition
2. Cut decomposition: A hinge+ decomposition bounded by the number of cuts
3. Traverse decomposition: Based on a simple sweep of the constraint hypergraph
4. Cut-and-Traverse decomposition: A combination of the cut and traverse
decompositions
s1 s2
s2
s6
s7
s9 s9 s10
s7 s7 s8 s8 s8 s
s12 s s s s9 9 s9 s15
13 13 14 s14 s
s13
9
s14
s s
s5
s
s1 s s2 s s 3 s s s
3 4 5 6
2
6
s3 s s s s
s2
11 s
5
4
11
s4
s11
s12 12
s6 s12
s6 s12 s17
Biconnected Component [3]
Hinge decomposition of Hcg
Cut-and-Traverse (CaT) Decomposition
Cut Decomposition
s6
s7
s9 s9 s10
s7 s7 s8 s8 s8 s
s12 s s s s9 9 s9 s15
13 13 14 s14 s
s13
9
s14
s s
Traverse Decomposition
We traverse a constraint hypergraph from a set F of hyperedges, until all the
hyperedges are visited as follows:

Start from Fs, mark all hyperedges whose vertices contained in Fs as ‘visited.’

Then traverse to Fs’s unvisited neighbors F1, mark all hyperedges whose
vertices contained in F1 as ‘visited.’

Then traverse to F1’s unvisited neighbors F2, mark all hyperedges whose
vertices contained in F2 as ‘visited.’

Continuously traversing until all the hyperedges are visited.
s1
s2
s3
s4
s5 s6 s7
s11 s12 s13
s17
s9
s10
s15
s8
s14
s16
s3
s4
s5 s6 s7
s11 s12 s13
s17
s8
s14
s9
s10
s15
s9
s16
A traverse decomposition for Hcg
starting from {s1, s2} to {s9, s16}.
Width of the join tree is 3.
Notice that traverse decomposition cannot guarantee a good decomposition result.
The result of the decomposition depends on the starting set of hyperedges and ending
set of hyperedges. The following graph shows a bad traverse decomposition.
s6
s9
s12
s5 s7
s8 s10
s14 s15 s16
s11 s12 s17
s3
s4
s1
2. Hinge+ decomposition strongly generalizes hinge decomposition.
3. Cut-and-traverse strongly generalizes cut decomposition.
4. Hypertree decomposition strongly generalizes hinge+ decomposition, traverse
decomposition, Cut-and-Traverse decomposition.
A traverse decomposition for Hcg
starting from {s1}.
Width of the join tree is 3.
We traverse a constraint hypergraph from a set Fs of hyperedges to another set of
hyperedges Fd as follows:

Start from Fs, mark all hyperedges whose vertices contained in Fs as ‘visited.’

Then traverse to Fs’s ‘unvisited’ neighbors and those hyperedges in Fd that has
common vertices with Fs, we denote them as F1, mark all hyperedges whose
vertices contained in F1 as ‘visited.’

Then traverse to F1’s ‘unvisited’ neighbors and those hyperedges in Fd that has
common vertices with F1, we denote them as F2, mark all hyperedges whose
vertices contained in F2 as ‘visited.’

Continuously traversing until traversing to Fd and all the hyperedges are visited.
s1
s2
1. All these decomposition methods can be performed in polynomial time.
Hinge+ decomposition O(|V||E|k+1)
Cut decomposition O(|V||E|k+1)
Traverse decompositionO(|V||E|2)
Cut-and-Traverse decompositionO(|V||E|k+1)
k is the limit size for cuts
A traverse decomposition for Hcg
starting from {s6, s9, s12}.
Width of the join tree is 10.
Future work
1. Empirically evaluate and compare the new proposed decomposition methods
on randomly generated constraint hypergraphs.
2. Compare cut-and-traverse decomposition method with
• hinge decomposition + tree clustering method, and
• hinge decomposition + biconnected component + hypertree decomposition.
References
1.
Gottlob, G., Leone, N., Scarcello, F. : On Tractable Queries and Constraints. In: 10th
International Conference and Workshop on Database and Expert System Applications
(DEXA 1999). (1999)
2. Decther, R.: Constraint Processing. Morgan Kaufmann (2003)
3. Freuder, E.C.: A Sufficient Condition for Backtrack-Bounded Search. JACM 32 (4) (1985)
4. Gyssens, M., Jeavons, P.G., Cohen, D.A.: Decomposing Constraint Satisfaction
Problems using Database Techniques. Artificial Intelligence 38 (1989)
5. Jeavons, P.G., Cohen, D.A., Gyssens, M. : A structural Decomposition for Hypergraphs.
Contemporary Mathematics 178 (1994)
6. Decther, R., Pearl. J: Tree Clustering for Constraint Networks. Artificial Intelligence 38
(1998) Gottlob, G., Leone, N., Scarcello, F.: Hypertree Decompositions and Tractable
Queries. Journal of Computer and System Sciences 64 (2002)
8. Harvey, P., Ghose, A.: Reducing Redundancy in the Hypertree Decomposition Scheme.
IEEE International Conference on Tools with Artificial Intelligence (ICTAI 03). (2003)
9. Gottlob, G., Leone, N., Scarcello, F.: A comparison of Structural CSP Decomposition
Methods. Artifical Intelligence
124 (2000)
10. Gottlob, G., Hutle, M., Wotawa, F.: Combining Hypertree, Bicomp, And Hinge
Decomposition. ECAI 02 (2002)
11. Zheng, Y., Choueiry B.Y.: Cut-and-Traverse: A New Structural Decomposition Strategy
for Finite Constraint Satisfaction Problems. CSCLP 04 (2004).
9 16
Applying hinge+ decomposition to Hcg.
September 8, 2004
This research is supported by CAREER Award #0133568
from the National Science Foundation.