Constraint satisfaction dual problem: Difference between revisions

Revision as of 01:28, 18 December 2009

Latest revision as of 20:06, 22 February 2025

(11 intermediate revisions by 7 users not shown)

Line 3:

==The dual problem==

The dual problem of a constraint satisfaction problem contains a variable for each constraint of the original problem. Its domains and constraints are built so to enforce a sort of equivalence to the original problem. In particular, the ___domain of a variable of the dual problem contains one element for each [[tuple]] satisfying the corresponding original constraint. This way, a dual variable can take a value if and only if the corresponding original constraint is satisfied by the corresponding tuple.

The constraints of the dual problem forbid two dual variables to take values that correspond to two incompatible tuples. Without these constraints, one dual variable may take the value corresponding to the tuple <math>x=1,y=2</math> while another dual variable takes the value corresponding to <math>y=3,z=1</math>, which assigns a different value to <math>y</math>.

Line 27:

In the dual problem, all constraints are binary. They all enforce two values, which are tuples, to agree on one or more original variables.

The ''dual graph'' is a representation of how variables are constrained in the dual problem. More precisely, the [[dual graph]] contains a node for each dual variable and an edge for every constraint between them. In addition, the edge between two variables is labeled by the original variables that are enforced equal between these two dual variables.

The dual graph can be built directly from the original problem: it contains a vertex for each constraint, and an edge between every two constraints sharing variables; such an edge is labeled by these shared variables.

Line 60:

Not all constraint satisfaction problems have a join tree. However, problems can be modified to acquire a join tree. [[Join-tree clustering]] is a specific method to modify problems in such a way they acquire a joint tree. This is done by merging constraints, which typically increases the size of the problem; however, solving the resulting problem is easy, as it is for all problems that have a join tree.

[[Decomposition method (constraint satisfaction)|Decomposition method]]s generalize join-tree clustering by grouping variables in such a way the resulting problem has a join tree. Decomposition methods directly associate a tree with problems; the nodes of this tree are associated varibablesvariables and/or constraints of the original problem. By merging constraints based on this tree, one can produce a problem that has a join tree, and this join tree can be easily derived from the decomposition tree. Alternatively, one can build a binary acyclic problem directly from the decomposition tree.

==References==

Line 71:

| year=2003

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

}} {{ISBN |978-1-55860-890-0}}

*{{cite book

| first=Rod

| last=Downey

| coauthorsauthor2=M. 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 |978-0-387-94883-6}}

*{{cite conference

| authorauthor1=Georg Gottlob, |author2=Nicola Leone, |author3=Francesco Scarcello | title=Hypertree Decompositions: A Survey

| booktitlebook-title=MFCS 2001

| title=Hypertree Decompositions: A Survey

| 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}}

}}

== See also ==

* [[Hidden transformation]]

[[Category:Constraint programming|satisfaction dual problem]]