From: Marco Gavanelli <marco.gavanelli_at_unife.it>

Date: Fri, 26 Oct 2007 12:29:22 +0200

Received on Fri Oct 26 2007 - 11:29:41 CEST

Date: Fri, 26 Oct 2007 12:29:22 +0200

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/

- text/plain attachment: dual.ecl

*
This archive was generated by hypermail 2.2.0
: Thu Feb 02 2012 - 02:31:58 CET
*