# Propagation of Arithmetic Constraints

From: Karen Petrie <k.e.petrie_at_hud.ac.uk>
Date: Sat 07 Feb 2004 05:55:37 PM GMT
```Hi all,

I have a constraint linking two sets of variables together. Binary variables x_{i,j} :: [0,1] and variables y_{i,j} :: [0..511].

The constraint is (using fd library):

y_{i,j} #= x_{i,j} +  (2 * x_{i,j+1}) + (4 * x_{i,j+2}) + (8 * x_{i+1,j}) + (16 * x_{i+1,j+1}) + (32 * x_{i+1,j+2}) + (64 * x_{i+2,j}) + (128* x_{i+2,j+1}) + (256* x_{i+2,j+2})

The y variables are the search variables. On a value being set for the y variable I would expect each of the x variables to automatically be set, but on looking at the seach through the visulisation tools this does not seem to be the case.

I have also tried decomposing the constraint into:

y_{i,j} #= (256* x_{i+2,j+2}) + W1
W1 #= (128* x_{i+2,j+1}) + W2
W2 #= (64 * x_{i+2,j}) + W3
W3 #= (32 * x_{i+1,j+2}) + W4
W4 #= (16 * x_{i+1,j+1}) + W5
W5 #= (8 * x_{i+1,j}) + W6
W6 #= (4 * x_{i,j+2}) + W7
W7 #= (2 * x_{i,j+1}) + W8
W8 #= x_{i,j}

Where:

W1 :: 0..255
W2 :: 0..127
W3 :: 0..63
W4 :: 0..31
W5 :: 0..15
W6 :: 0..7
W7 :: 0..3
W8 :: 0,1

It is also possible to decompose this constraint using modular aritmetic so that each x variable is assigned a value based on the corresponding y variables. But this would introduce a large number of constraints that do not seem needed.

Obviously, the fact that the x variables are not being automatically set by assigning a value to the y variable, is slowing down search considerably. I wonder if anyone can suggest why this is not the case and perhaps come up with a work-around?

Thank you, in anticipation of your help,

Karen

---
This transmission is confidential and may be legally privileged. If you receive it in
error, please notify us immediately by e-mail and remove it from your system. If
the content of this e-mail does not relate to the business of the University of
Huddersfield, then we do not endorse it and will accept no liability.
```
Received on Sat Feb 07 18:04:04 2004

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:27 PM GMT GMT