Content deleted Content added
GreenC bot (talk | contribs) Reformat 1 archive link. Wayback Medic 2.5 per Category:All articles with dead external links - pass 6 |
Link suggestions feature: 2 links added. Tags: Visual edit Mobile edit Mobile web edit Newcomer task Suggested: add links |
||
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.
| |||