INTEGER PROGRAMMING:The All-Different Constraint

The All-Different Constraint

The all-different global constraint simply specifies that all the variables in a given set must have different values. If x1, x2, . . . , xn are the variables involved, the constraint can be written succinctly as all-different (x1, x2, . . . , xn)

while also specifying the domains of the individual variables in the model. (These domains collectively need to include at least n different values in order to enforce the all-different constraint.)

To illustrate this constraint, consider the classical assignment problem presented in Sec. 9.3. Recall that this problem involves assigning n assignees to n tasks on a one- to-one basis so as to minimize the total cost of these assignments. Although the as- signment problem is a particularly easy one to solve (as described in Sec. 9.4), it nicely illustrates how the all-different constraint can greatly simplify the formulation of the model.

With the traditional formulation presented in Sec. 9.3, the decision variables are the binary variables, for i, j = 1, 2, . . . , n. Ignoring the objective function for now, the functional constraints are the following.

Each assignee i is to be assigned to exactly one task:

Thus, there are n2 variables and 2n functional constraints.

Now let us look at the much smaller model that constraint programming can provide.

In this case, the variables are yi = task to which assignee i is assigned for i = 1, 2, . . . , n. There are n tasks and they are numbered 1, 2, . . . , n, so each of the yi variables has the domain {1, 2, . . . , n}. Since all the assignees must be assigned different tasks, this restriction on the variables is precisely described by the single global constraint, all-different (y1, y2, . . . , yn).

Therefore, rather than n2 variables and 2n functional constraints, this complete constraint programming model (excluding the objective function) has only n variables and a single constraint (plus one domain for all the variables).

Now let us see how the next global constraint enables incorporating the objective function into this tiny model as well.