Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 01:36, 30 July 2016

Latest revision as of 06:51, 26 January 2025

(15 intermediate revisions by 14 users not shown)

Line 1:

{{More citations needed|date=June 2019}}

In [[constraint satisfaction]], a '''decomposition method''' translates a [[constraint satisfaction problem]] into another constraint satisfaction problem that is binary and [[directed acyclic graph|acyclic]]. Decomposition methods work by grouping variables into sets, and solving a subproblem for each set. These translations are done because solving binary acyclic problems is a [[tractable problem]].

Line 33 ⟶ 35:

|-

| [[Image:Tree-decomposition-4.svg]]

| 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 <math>y</math> is shown: the corresponding constraint is only met by the first tuple of <math>(x,y,z)</math> and the first tuple of <math>(y,w)</math>, and by the second tuple of <math>(x,y,z)</math> and the second tuple of <math>(y,w)</math>. Moreover, the second tuple of<math> (x,y,z)</math> cannot find a satisfied tuple in its left child (<math> (u,x,z)</math>). Thus, the second tuple of <math>(u,x,z)</math> should be removed.

|}

Line 104 ⟶ 106:

===Cycle hypercutset===

This is the same mathodmethod of cycle cutset using the definition of cutset for hypergraphs: a cycle hypercutset of a hypergraph is a set of edges (rather than vertices) that makes the hypergraph acyclic when all their vertices are removed. A decomposition can be obtained by grouping all variables of a hypercutset in a single one. This leads to a tree whose nodes are sets of hyperedges. The width of such a decomposition is the maximal size of the sets associated with nodes, which is one if the original problem is acyclic and the size of its minimal hypercutset otherwise. The width of a problem is the minimal width of its decompositions.

===Hinge decomposition===

AnA hinge is a subset of nodes of hypergraph having some properties defined below. AnA hinge decomposition is based on the sets of variables that are minimal hinges of the hypergraph whose nodes are the variables of the constraint satisfaction problem and whose hyperedges are the scopes of its constraints.

The definition of hinge is as follows. Let <math>H</math> be a set of hyperedges. A path w.r.t.with respect to <math>H</math> is a sequence of edges such that the intersection of each one with the next one is non-empty and not contained in the nodes of <math>H</math>. A set of edges is connected w.r.t.with respect to <math>H</math> if, for each pair of its edges, there is a path w.r.t.with respect to <math>H</math> of which the two nodes are the first and the last edge. A connected component w.r.t.with respect to <math>H</math> is a maximal set of connected edges with respect to <math>H</math>.

Hinges are defined for reduced hypergraphs, which are hypergraphs where no hyperedge is contained in another. A set of at least two edges <math>H</math> is a hinge if, for every connected component <math>F</math> w.r.t.with respect to <math>H</math>, all nodes in <math>F</math> that are also in <math>H</math> are all contained in a single edge of <math>H</math>.

AnA hinge decomposition is based on the correspondence between constraint satisfaction problems and hypergraphs. The hypergraph associated with a problem has the variables of the problem as nodes are the scopes of the constraints as hyperedges. AnA hinge decomposition of a constraint satisfaction problem is a tree whose nodes are some minimal hinges of the hypergraph associated to the problem and such that some other conditions are met. By the correspondence of problems with hypergraphs, a hinge is a set of scopes of constraints, and can therefore be considered as a set of constraints. The additional conditions of the definition of a hinge decomposition are three, of which the first two ensure equivalence of the original problem with the new one. The two conditions for equivalence are: the scope of each constraint is contained in at least one node of the tree, and the subtree induced by a variable of the original problem is connected. The additional condition is that, if two nodes are joined, then they share exactly one constraint, and the scope of this constraint contains all variables shared by the two nodes.

The maximal number of constraints of a node is the same for all hinge decompositions of the same problem. This number is called the ''degree of cyclicity'' of the problem or its hingewidth.

Line 217 ⟶ 219:

In a tree, every edge breaks the graph in two parts. The constraint passed along an edge tells how the part of the originating end of the edge affects the variables of the destination node. In other words, a constraint passed from node <math>i</math> to node <math>j</math> tells how the nodes "on the side of <math>i</math>" constrain the variables of node <math>j</math>.

If the variables of these two nodes are <math>X_i</math> and <math>X_j</math>, the nodes on the sizeside of <math>i</math> do not affect all variables <math>X_j</math> but only the shared variables <math>X_i \cap X_j</math>. As a result, the influence on <math>X_j</math> of the nodes on the side of <math>i</math> can be represented as a constraint on variables <math>X_i \cap X_j</math>. Such a constraint can be seen as a "summary" of how a set of nodes affects another node.

The algorithm proceeds from the leaves of the tree. In each node, the summaries of its children (if any) are collected. These summary and the constraint of the node are used to generate the summary of the node for its parent. When the root is reached, the process is inverted: the summary of each node for each child is generated and sent it. When all leaves are reached, the algorithm stops.

Line 268 ⟶ 270:

# [http://www.cs.uu.nl/research/projects/treewidthlib/ Treewidthlib]: A benchmark for algorithms for Treewidth and related graph problems

# [https://web.archive.org/web/20060512022851/http://www.ics.uci.edu/~vgogate/ A C++ implementation] used in the paper "A complete [[Anytime Algorithm]] for Treewidth, Vibhav Gogate and Rina Dechter, UAI 2004." [https://web.archive.org/web/20060512022851/http://www.ics.uci.edu/~vgogate/ The link] is to the author homepage, where both LINUX source and Windows executable is distributed.

# [http://www.dbai.tuwien.ac.at/proj/hypertree/downloads.html An implementation of Hypertree Decomposition], using several heuristics.

# [http://carlit.toulouse.inra.fr/cgi-bin/awki.cgi/ToolBarIntro Toolbar tool has implementation of some tree decomposition heuristics]

Line 278 ⟶ 280:

| first=Rina

| last=Dechter

|authorlink = Rina Dechter

| title=Constraint Processing

| publisher=Morgan Kaufmann

| year=2003

| url=http://www.ics.uci.edu/~dechter/books/index.html

}} {{ISBN |1-55860-890-7}}

*{{cite book

| firstfirst1=Rod

| lastlast1=Downey

|author1link = Rod Downey

|author2=Michael Fellows

|first2=Michael

|last2 = Fellows

|author2author2link = Michael Fellows

| title=Parameterized complexity

| publisher=Springer

| year=1997

| url=httphttps://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html?referer=www.springer.de%2Fcgi-bin%2Fsearch_book.pl%3Fisbn%3D0-387-94883-X

}} {{ISBN |0-387-94883-X}}

*{{cite conference

| first=Georg

| last=Gottlob

|author1link = Georg Gottlob

|author2=Nicola Leone |author3=Francesco Scarcello

|first2=Nicola|last2 = Leone

|author2link = Nicola Leone

|first3=Francesco| last3 = Scarcello

| title=Hypertree Decompositions: A Survey

| book-title=[[International Symposium on Mathematical Foundations of Computer Science|MFCS]] 2001

| booktitle=MFCS 2001

| pages=37–57

| year=2001

| url=http://www.springerlink.com/(rqc54x55rqwetq55eco03ymp)/app/home/contribution.asp?referrer=parent&backto=issue,5,61;journal,1765,3346;linkingpublicationresults,1:105633,1

}}{{dead link|date=January 2025|bot=medic}}{{cbignore|bot=medic}}

}}

*{{cite journal

| first=Georg

| last=Gottlob

|author2first2=Nicola|last2 = Leone |author3first3=Francesco| last3 = Scarcello

| title=A comparison of structural CSP decomposition methods

| journal=[[Artificial Intelligence (journal)|Artificial Intelligence]]

| volume=124

| issue=2

| pages=243–282

| year=2000

| doi=10.1016/S0004-3702(00)00078-3}}| doi-access=free

}}

[[Category:Constraint programming]]