<< Prev | - Up - | Next >> |

Not all propagators exploit coreferences in products (e.g. ). For the example of this section it will be essential to exploit such coreferences, and you will learn how to do it.

The example also illustrates the case where a propagator for a redundant constraint improves the performance of a script by decreasing the number of necessary propagation steps, but without significantly changing the search tree.

How many triples exist such that\ and ?

The model has three variables , , and . Each variable is constrained to the finite domain . The model imposes the constraints and .

The script will also create a propagator for the redundant constraint .

We distribute on the variables , , using the standard first-fail strategy.

`proc {Square X S}`

{FD.times X X S}

end

`proc {Pythagoras Root}`

[A B C] = Root

AA BB CC

in

Root ::: 1#1000

AA = {Square A}

BB = {Square B}

CC = {Square C}

AA + BB =: CC

A =<: B

B =<: C

2*BB >=: CC % redundant constraint

{FD.distribute ff Root}

end

Given the script in Figure 7.2, we can compute the number of different triples with the statement

`{Browse {Length {SearchAll Pythagoras}}}`

The script introduces a defined constraint

`{Square X S}`

saying that `S`

is the square of `X`

. This constraint is implemented with a propagator provided by

`{FD.times X X S}`

This propagator will start propagating as soon as the store constrains `X`

to a finite domain. This in contrast to the propagator created by `X*X=:S`

, which will start work only after both `X`

and `S`

are constrained to finite domains in the constraint store. To define `Square`

with this constraint, we would have to write

`proc {Square X S}`

{FD.decl S}

X*X =: S

end

The propagator for the redundant constraint does not significantly reduce the size of the search tree. However, it reduces the number of propagation steps from about 1000000 to about 500000, which makes computation twice as fast.

statistics

To find out about this, pop up the Oz Panel and reset the statistics. Also switch on the status message feature and pop up the emulator buffer. Now enter the statement

`{Browse {Length {SearchAll Pythagoras}}}`

and print the statistics after the execution of the statement has finished. This will show something like

`solutions: 881 Variables created: 3`

clones: 1488 Propagators created: 7

failures: 608 Propagator invocations: 490299

in the emulator buffer. Now remove the propagator for the redundant constraint from the definition of the script, redefine it, reset the statistics, run the statement, and print the statistics. This time you will see something like

`solutions: 881 Variables created: 3`

clones: 1878 Propagators created: 6

failures: 998 Propagator invocations: 1190397

If we drop the redundant constraint, it seems sensible to not have separate propagators for the squares but simply have one propagator created with

`A*A + B*B =: C*C`

Unfortunately, this will dramatically increase the size of the search tree. The reason for this increase is the fact that the created propagator does not realize the coreferences in the constraint it implements, that is, it treats the two occurrences of `A`

, say, as if they were independent variables.

<< Prev | - Up - | Next >> |

Christian Schulte and Gert Smolka

Version 1.4.0 (20080702)