IBM ILOG Solver User's Manual > The Basics > Constraint Programming with IBM ILOG Solver > Solve > Initial constraint propagation |
Initial constraint propagation |
INDEX
![]() |
First, Solver performs an initial constraint propagation. The initial constraint propagation removes all values from domains that will not take part in any solution. Before propagation, the domains are:
D(x) = [5 6 7 8 9 10 11 12] D(y) = [2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17] |
To get an idea of how initial constraint propagation works, consider the constraint x + y = 17. If you take the smallest number in the domain of x, which is 5, and add it to the largest number in the domain of y, which is 17, the answer is 22. This combination of values (x = 5, y = 17) violates the constraint x + y = 17. The only value of x that would work with y = 17 is x = 0. However, there is no value of 0 in the domain of x, so y cannot be equal to 17. The value y = 17 cannot take part in any solution. Solver removes the value y = 17 from the domain of y. Similarly, Solver removes the following values from the domain of y: 13, 14, 15, and 16.
Likewise, if you take the largest number in the domain of x, which is 12, and add it to the smallest number in the domain of y, which is 2, the answer is 14. This combination of values (x = 12, y = 2) violates the constraint x + y = 17. The only value of x that would work with y = 2 is x = 15. However, there is no value of 15 in the domain of x, so y cannot be equal to 2. The value of y = 2 cannot take part in any solution. Solver removes the value y = 2 from the domain of y. For the same reason, Solver removes the following values from the domain of y: 2, 3, and 4.
After initial propagation for the constraint x + y = 17, the domains are:
D(x) = [5 6 7 8 9 10 11 12] D(y) = [5 6 7 8 9 10 11 12] |
Now, examine the constraint x - y = 5. If you take the value 5 in the domain of x, you can see that the only value of y that would work with x = 5 is y = 0. However, there is no value of 0 in the domain of y, so x cannot equal 5. The value x = 5 cannot take part in any solution. Solver removes the value x = 5 from the domain of x. Using similar logic, Solver removes the following values from the domain of x: 6, 7, 8, and 9. Likewise, Solver removes the following values from the domain of y: 8, 9, 10, 11, and 12.
After initial propagation for both constraints, the search space has been greatly reduced in size. The domains are now:
D(x) = [10 11 12] D(y) = [5 6 7] |
© Copyright IBM Corp. 1987, 2009. Legal terms. | PREVIOUS NEXT |