Re: [eclipse-users] Dual Enconding CSP

Christian Riquelme wrote:
> Hi, sorry my bad english, i'm trying to code a CSP with dual encoding, but i
> dont know how define the restriction and variables in this case.
> 
> This is the problem
> 
> http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume24/samaras05a-html/node7.html
> 
> i think for variables..
> 
> [V1]::[(0,0,1),(0,1,0),(1,0,0)],
> [V2]::[(0,0,1),(1,0,0),(1,1,1)],
> [V3]::[(0,1,0),(1,0,0),(1,1,0),(1,1,1)],
> [V4]::[(0,0,0),(0,1,1),(1,0,1)],
> 
> restriction ????

Dear Christian,

some time ago I wrote an implementation of a dual constraint; I am 
sending it as an attachment. Sorry, the comments are in Italian.

Basically, you have to state that each variable of the primal CSP takes 
one value.

Variables in the dual CSP represent allowed tuples in the (primal) 
constraint. In your example, V1 corresponds to a constraint c1: 
X1+X2+X6#=1, and thus V1 can take the value (0,0,1), which satisfies the 
constraint c1. This means that you can assign X1=0, X2=0, X6=1 and c1 is 
satisfied. Same for V2, that corresponds to the constraint c2: X1-X3+X4 
#= 1.

Now, you have to state that variable X1 takes the same value in both 
constraints c1 and c2, i.e., that the first element in the tuple 
assigned to V1 is equal to the first element in the tuple assigned to 
V2. In order to impose this condition, you can use the (attached) constraint

	dual_ac(V1,1,V2,1)

So, considering only the first two variables V1 and V2:

[eclipse 2]: [V1]::[(0,0,1),(0,1,0),(1,0,0)],
	[V2]::[(0,0,1),(1,0,0),(1,1,1)],
         dual_ac(V1,1,V2,1).

V1 = V1{[(0, 0, 1), (0, 1, 0), (1, 0, 0)]}
V2 = V2{[(0, 0, 1), (1, 0, 0), (1, 1, 1)]}


Delayed goals:
         dual_ac(V1{[(0, 0, 1), (0, 1, 0), (1, 0, 0)]}, 1, V2{[(0, 0, 
1), (1, 0, 0), (1, 1, 1)]}, 1)
Yes (0.00s cpu)
[eclipse 3]: [V1]::[(0,0,1),(0,1,0),(1,0,0)],
	[V2]::[(0,0,1),(1,0,0),(1,1,1)],
         dual_ac(V1,1,V2,1), labeling([V1,V2]).

V1 = 0, 0, 1
V2 = 0, 0, 1
Yes (0.00s cpu, solution 1, maybe more) ? ;

V1 = 0, 1, 0
V2 = 0, 0, 1
Yes (0.00s cpu, solution 2, maybe more) ? ;

V1 = 1, 0, 0
V2 = 1, 0, 0
Yes (0.00s cpu, solution 3, maybe more) ? ;

V1 = 1, 0, 0
V2 = 1, 1, 1
Yes (0.00s cpu, solution 4)

Cheers,
Marco

-- 
Marco Gavanelli, Ph.D.
Computer Science Division
Dipartimento di Ingegneria
University of Ferrara
Via Saragat 1 - 44100 Ferrara (Italy)
Tel  +39-0532-97-4833
Fax  +39-0532-97-4870
http://www.ing.unife.it/docenti/MarcoGavanelli/