One powerful feature of constraint programming is that variables can be used as subscripts for the terms in the objective function. For example, consider the following traveling salesman problem. The salesman needs to visit each of n cities (city 1, 2, . . . ,n) exactly once, starting in city 1 (his home city) and returning to city 1 after completing the tour. Let cij be the distance from city i to city j for i, j = 1, 2, . . . , n (i ‰  j). The objective is to determine which route to follow so as to minimize the total distance of the tour. (As discussed further in Chap. 14, this traveling salesman problem is a famous classic OR problem with many applications that have nothing to do with salesmen.) Letting the decision variable xj (j = 1, 2, . . . ,n, n = 1) denote the jth city visited by the salesman, where x1 = 1 and xn = 1 = 1, constrant programming allows writing the objective as

Using this objective function, formulate a complete constraint programming model for this problem.

Transcribed Image Text:

Minimize Z = . ー