The Element Constraint

The Element Constraint

The element global constraint is most commonly used to look up a cost or profit associated with an integer variable. In particular, suppose that a variable y has domain {1, 2, . . . , n} and that the cost associated with each of these values is c1, c2, . . . , cn, respectively. Then the constraint

element (y, [c1, c2, . . . , cn], z)

constrains the variable z to equal the yth constant in the list [c1, c2, . . . , cn]. In other words, z = cy. This variable z can now be included in the objective function to provide the cost associated with y.

To illustrate the use of the element constraint, consider the assignment problem again and let

cij = cost of assigning assignee i to task j

for i, j, = 1, 2, . . . , n. The complete constraint programming model (including the ob- jective function for this problem is

Minimize Z = Izi,

i=1

subject to

element (yi, [ci1, ci2, . . . , cin], zi) for i = 1, 2, . . . , n, all-different (y1, y2, . . . , yn),

yi ∈ {1, 2, . . . , n} for i = 1, 2, . . . , n.

This complete model now has 2n variables and (n + 1) constraints (plus the one domain for all the variables), which still is far smaller than the traditional integer programming formulation presented in Sec. 9.3. For example, when n = 100, this model has 200 variables

and 101 constraints whereas the traditional integer programming model has 10,000 variables and 200 functional constraints.

As an additional example, reconsider Example 2 (Violating Proportionality) presented in Sec. 12.4. In this case, the original decision variables are

xj = number of TV spots allocated to product j

for j = 1, 2, 3, where a total of five TV spots are to be allocated to the three products. However, because the profits given in Table 12.3 for different values of each xj are not proportional to xj, Sec. 12.4 formulates two alternative integer programming models with auxiliary binary variables for this problem. Both models are fairly complicated.

A constraint programming model that uses the element constraint is much more straightforward. For example, the profit for Product 1 given in Table 12.3 is 0, 1, 3, and 3 for x1 = 0, 1, 2, and 3, respectively. Therefore, this profit is simply z1 when the value of z1 is given by the constraint

Now compare this model to the two integer programming models for the same prob- lem in Sec. 12.4. Note how the use of element constraints provides a considerably more compact and transparent model.

The all-different and element constraints are but two of the various available global constraints (Selected Reference 5 describes nearly 40), but they nicely illustrate the power of constraint programming to provide a compact and readable model of a complex problem.