L20: Cost of GAC

Question 1

Is GAC expensive?

Answer 1

Yes.
It can be expensive for many constraints, in particular numerical constraints.

Question 2

What is an alternative to GAC?

Answer 2

Bound consistency is a cheaper alternative.

Question 3

What is bound consistency?

Answer 3

Bound consistency is a cheaper version of GAC where only the minimum and maximum values (bounds) of a domain are being pruned.

Question 4

What does bound consistency assume?

Answer 4

We are also assuming that the bounds are an unbroken interval between [a,b] where the domain contains all integers i in a<=i<=b (no missing values in between).

Question 5

What is bound(d)-consistency?

Answer 5

Same as definition of GAC, except that only bounds are supported.

Question 6

What is bound(z)-consistency?

Answer 6

Same as definition of Bound(D)-consistency, except that values in t are only required to be between the bounds of the corresponding variable.

Question 7

What is bound(r)-consistency?

Answer 7

Same as definition of Bound(Z)-consistency, except that values in t may be non-integer.