Search code examples
prologclpfd

What is bounds propagation in clpfd

I am trying to figure out what is bounds propagation in , but cannot seem to find a good explanation anywhere.

I am revising for Prolog and clpfd and came across this question, but looking at the lecture notes it does not make sense to me. Could someone please explain the actual meaning of bounds propagation and what it is used for.

Here is the question I am referring to:

When the following Prolog program

:- use_module(library(clpfd)).
bounds(X, Y, Z) :-
   X in 1..5,
   Y in 1..2,
   Z in 3..5,
   X #= Y + Z.
is queried it gives the answer:

?- bounds(X, Y, Z).
X in 4..5,
Y in 1..2,
Z in 3..4.

Explain how bounds propagation can be applied to infer this answer.

Solution

  • I give you a start:

    After all constraints are posted, one thing is immediately clear: X is at least 4. Why? Because Y is at least 1, and Z is at least 3, and X is the sum of Y and Z.

    Given this knowledge, go through the posted constraints again, and see if you can adjust any boundaries.

    This is what bounds propagation does: going through the boundaries of all variables and seeing if any of them can be adjusted due to the posted constraints. This is repeated until there are no more possible domain reductions.