PyCSP3

type: COP

# Problem Traveling Tournament

Given n teams (n being even), a round-robin tournament is a tournament among the teams so that every team plays each other team. Such a tournament has n-1 rounds (slots or weeks) during which n/2 games are played. For each game, one team is denoted the home team and its opponent the away team. A double-robin tournament has 2(n-1) rounds and has every pair of teams playing twice, once at home and the once away.  Distances between team sites are given by an n by n distance matrix. When a teams plays an away game, it is assumed to travel from its home site to the away venue. When playing consecutive away games, teams travel from one away venue to the next directly. It is forbidden for a team to play more than two consecutive times at home or away. The sum of the traveling distance of each team has to be minimized.

Traveling Tournament. Image from freesvg.org To build a COP (Constraint Optimization Problem) model, we need first to import the library PyCSP$^3$:

from pycsp3 import *


Then, we need some data. In our case, this is distance matrix.

distances = [
[0,10,15,34],
[10,0,22,32],
[15,22,0,47],
[34,32,47,0]
]


We define a few constants.

nTeams = len(distances)
nRounds = len(distances) * 2 - 2
assert nTeams % 2 == 0, "An even number of teams is expected"


We gently start our COP model with a two-dimensional array $o$ of $4 \times 6$ variables. This will allow us to represent, for any team $i$, its opponent at every round.

# o[i][k] is the opponent (team) of the ith team at the kth round
o = VarArray(size=[nTeams, nRounds], dom=range(nTeams))


We can display (the structure of) this array as well as the domain of the involved variables.

print("Array of variable o: ", o)
print("Domain of any variable in o: ", o.dom)

Array of variable o:  [
[o, o, o, o, o, o]
[o, o, o, o, o, o]
[o, o, o, o, o, o]
[o, o, o, o, o, o]
]
Domain of any variable in o:  0..3


## Setting Games

Concerning the constraints, we first post a group of constraints Cardinality.

satisfy(
# each team must play exactly two times against each other team
Cardinality(o[i], occurrences={j: 2 for j in range(nTeams) if j != i}) for i in range(nTeams)
);


We can display the internal representation of the posted constraints; this way, although a little bit technical, we can check that the constraints are correctly posted.

print(posted())

cardinality(list:[o, o, o, o, o, o], values:[1, 2, 3], occurs:[2, 2, 2])
cardinality(list:[o, o, o, o, o, o], values:[0, 2, 3], occurs:[2, 2, 2])
cardinality(list:[o, o, o, o, o, o], values:[0, 1, 3], occurs:[2, 2, 2])
cardinality(list:[o, o, o, o, o, o], values:[0, 1, 2], occurs:[2, 2, 2])


Interestingly, by calling the function solve(), we can check that the problem is satisfiable (SAT). We can also display the values of variables in $o$. Here, we call the function values() that collects the values assigned to a specified list of variables.

if solve() is SAT:
print(values(o))

[
[1, 1, 2, 2, 3, 3]
[0, 0, 2, 2, 3, 3]
[0, 0, 1, 1, 3, 3]
[0, 0, 1, 1, 2, 2]
]


In this first “solution”, one can see that much remains to be done. For example, if we have team i playing against team j at round k, then team j must play against i at the same round.

We need some constraints Element to capture this.

satisfy(
# ensuring symmetry of games: if team i plays against j at round k, then team j plays against i at round k
o[o[i][k]][k] == i for i in range(nTeams) for k in range(nRounds)
);


By calling posted(-1) we can get the constraints that have been posted during the last call to satisfy().

print(posted(-1))

element(list:[o, o, o, o], index:o, condition:(eq,0))
element(list:[o, o, o, o], index:o, condition:(eq,0))
element(list:[o, o, o, o], index:o, condition:(eq,0))
element(list:[o, o, o, o], index:o, condition:(eq,0))
element(list:[o, o, o, o], index:o, condition:(eq,0))
element(list:[o, o, o, o], index:o, condition:(eq,0))
element(list:[o, o, o, o], index:o, condition:(eq,1))
element(list:[o, o, o, o], index:o, condition:(eq,1))
element(list:[o, o, o, o], index:o, condition:(eq,1))
element(list:[o, o, o, o], index:o, condition:(eq,1))
element(list:[o, o, o, o], index:o, condition:(eq,1))
element(list:[o, o, o, o], index:o, condition:(eq,1))
element(list:[o, o, o, o], index:o, condition:(eq,2))
element(list:[o, o, o, o], index:o, condition:(eq,2))
element(list:[o, o, o, o], index:o, condition:(eq,2))
element(list:[o, o, o, o], index:o, condition:(eq,2))
element(list:[o, o, o, o], index:o, condition:(eq,2))
element(list:[o, o, o, o], index:o, condition:(eq,2))
element(list:[o, o, o, o], index:o, condition:(eq,3))
element(list:[o, o, o, o], index:o, condition:(eq,3))
element(list:[o, o, o, o], index:o, condition:(eq,3))
element(list:[o, o, o, o], index:o, condition:(eq,3))
element(list:[o, o, o, o], index:o, condition:(eq,3))
element(list:[o, o, o, o], index:o, condition:(eq,3))


we can run again the solver.

if solve() is SAT:
print(values(o))

[
[1, 1, 2, 2, 3, 3]
[0, 0, 3, 3, 2, 2]
[3, 3, 0, 0, 1, 1]
[2, 2, 1, 1, 0, 0]
]


This is better. But for the moment, we have no information at all about which teams play home and which teams play away.

## Handling Home and Away Games

We now need to introduce a two-dimensional array $h$ of $4 \times 6$ variables. This will allows us to represent, for any team $i$, its situation (home or away) at every round.

# h[i][k] is 1 iff the ith team plays at home at the kth round
h = VarArray(size=[nTeams, nRounds], dom={0, 1})


We can display (the structure of) this array as well as the domain of any involved variable.

print("Array of variable h: ", h)
print("Domain of any variable in h: ", h.dom)

Array of variable h:  [
[h, h, h, h, h, h]
[h, h, h, h, h, h]
[h, h, h, h, h, h]
[h, h, h, h, h, h]
]
Domain of any variable in h:  0 1


At any round, the opponent of team i plays at home if i plays away, and vice versa. To capture this, we use a group of constraints Element.

satisfy(
# channeling the arrays o and h
h[o[i][k]][k] != h[i][k] for i in range(nTeams) for k in range(nRounds)
);


We display the first 8 constraints that have been posted in this group.

print(posted(-1)[:8])

element(list:[h, h, h, h], index:o, condition:(ne,h))
element(list:[h, h, h, h], index:o, condition:(ne,h))
element(list:[h, h, h, h], index:o, condition:(ne,h))
element(list:[h, h, h, h], index:o, condition:(ne,h))
element(list:[h, h, h, h], index:o, condition:(ne,h))
element(list:[h, h, h, h], index:o, condition:(ne,h))
element(list:[h, h, h, h], index:o, condition:(ne,h))
element(list:[h, h, h, h], index:o, condition:(ne,h))


We run the solver.

if solve() is SAT:
print("Opponents: ", values(o))
print("Playing at home: ", values(h))

Opponents:  [
[1, 1, 2, 2, 3, 3]
[0, 0, 3, 3, 2, 2]
[3, 3, 0, 0, 1, 1]
[2, 2, 1, 1, 0, 0]
]
Playing at home:  [
[0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
]


We can print something more readable.

if solve() is SAT:
for k in range(nRounds):
matches = [(i,o[i][k].value) for i in range(nTeams) if h[i][k].value == 1]
print(f"Matches at Round {k}: {matches}")

Matches at Round 0: [(1, 0), (3, 2)]
Matches at Round 1: [(1, 0), (3, 2)]
Matches at Round 2: [(2, 0), (3, 1)]
Matches at Round 3: [(2, 0), (3, 1)]
Matches at Round 4: [(2, 1), (3, 0)]
Matches at Round 5: [(2, 1), (3, 0)]


We have a problem because some teams play more often at home than others. We can fix this problem by posting a group of constraints Intension.

satisfy(
# playing against the same team must be done once at home and once away
imply(o[i][k1] == o[i][k2], h[i][k1] != h[i][k2]) for i in range(nTeams)
for k1, k2 in combinations(range(nRounds), 2)
);


We display the 10 last posted constraints.

print(posted()[-10:])

intension(function:imp(eq(o,o),ne(h,h)))
intension(function:imp(eq(o,o),ne(h,h)))
intension(function:imp(eq(o,o),ne(h,h)))
intension(function:imp(eq(o,o),ne(h,h)))
intension(function:imp(eq(o,o),ne(h,h)))
intension(function:imp(eq(o,o),ne(h,h)))
intension(function:imp(eq(o,o),ne(h,h)))
intension(function:imp(eq(o,o),ne(h,h)))
intension(function:imp(eq(o,o),ne(h,h)))
intension(function:imp(eq(o,o),ne(h,h)))


We run the solver.

if solve() is SAT:
for k in range(nRounds):
matches = [(i,o[i][k].value) for i in range(nTeams) if h[i][k].value == 1]
print(f"Matches at Round {k}: {matches}")

Matches at Round 0: [(1, 0), (3, 2)]
Matches at Round 1: [(0, 1), (2, 3)]
Matches at Round 2: [(2, 0), (3, 1)]
Matches at Round 3: [(0, 2), (1, 3)]
Matches at Round 4: [(2, 1), (3, 0)]
Matches at Round 5: [(0, 3), (1, 2)]

It works. It may even that the constraint about a maximal sequence of two successive matches at home or away is respected. However, we need to guarantee it.


At this stage, we can compute the number of solutions: it is 5760.

## Handling Consecutive Matches at Home and Away

For ensuring that at most each team plays two times consecutively at home or away, we can impose, for every team i, a regular expression on the variables $h[i]$. We invite the reader to draw the automaton that corresponds to the one returned by the following function.

def automaton():
qi, q01, q02, q03, q11, q12, q13 = states = "q", "q01", "q02", "q03", "q11", "q12", "q13"
trs = [(qi, 0, q01), (qi, 1, q11), (q01, 0, q02), (q01, 1, q11),
(q11, 0, q01), (q11, 1, q12), (q02, 1, q11), (q12, 0, q01)]
return Automaton(start=qi, transitions=trs, final=states[1:])


We build the automaton.

A = automaton()


We can control the automaton by displaying it.

print(A)

Automaton(start=q, transitions={(q,0,q01),(q,1,q11),(q01,0,q02),(q01,1,q11),(q11,0,q01),(q11,1,q12),(q02,1,q11),(q12,0,q01)}, final=[q01,q02,q11,q12])


We post a group of constraints Regular.

satisfy(
# at most 2 consecutive games at home, or consecutive games away
h[i] in A for i in range(nTeams)
);


We display the last posted constraints.

print(posted(-1))

regular(list:[h, h, h, h, h, h], transitions:(q,0,q01)(q,1,q11)(q01,0,q02)(q01,1,q11)(q11,0,q01)(q11,1,q12)(q02,1,q11)(q12,0,q01), start:q, final:[q01, q02, q11, q12])
regular(list:[h, h, h, h, h, h], transitions:(q,0,q01)(q,1,q11)(q01,0,q02)(q01,1,q11)(q11,0,q01)(q11,1,q12)(q02,1,q11)(q12,0,q01), start:q, final:[q01, q02, q11, q12])
regular(list:[h, h, h, h, h, h], transitions:(q,0,q01)(q,1,q11)(q01,0,q02)(q01,1,q11)(q11,0,q01)(q11,1,q12)(q02,1,q11)(q12,0,q01), start:q, final:[q01, q02, q11, q12])
regular(list:[h, h, h, h, h, h], transitions:(q,0,q01)(q,1,q11)(q01,0,q02)(q01,1,q11)(q11,0,q01)(q11,1,q12)(q02,1,q11)(q12,0,q01), start:q, final:[q01, q02, q11, q12])

We run the solver.

if solve() is SAT:
for k in range(nRounds):
matches = [(i,o[i][k].value) for i in range(nTeams) if h[i][k].value == 1]
print(f"Matches at Round {k}: {matches}")

Matches at Round 0: [(1, 0), (3, 2)]
Matches at Round 1: [(0, 1), (2, 3)]
Matches at Round 2: [(2, 0), (3, 1)]
Matches at Round 3: [(0, 2), (1, 3)]
Matches at Round 4: [(2, 1), (3, 0)]
Matches at Round 5: [(0, 3), (1, 2)]


It may be the case that the solution is the same as previously as if the new constraints were useless (actually, this is mainly due to the small number of teams). However, if we compare the 5760 earlier solutions to the 2208 that we obtain now, can can see the real effect of the posted constraints Regular.

if solve(sols=ALL) is SAT:
print("Number of solutions: ", n_solutions())

Number of solutions:  2208


## Computing Traveled Distances

For dealing with distances traveled by teams at every round, we introduce a two-dimensional array $t$ $4 \times 7$ variables.

# t[i][k] is the travelled distance by the ith team at the kth round.
# An additional round is considered for returning at home.
t = VarArray(size=[nTeams, nRounds + 1], dom=distances)


The structure of this array and the domain of the involved variables are as follows:

print("Array of variable t: ", t)
print("Domain of any variable in t: ", t.dom)

Array of variable t:  [
[t, t, t, t, t, t, t]
[t, t, t, t, t, t, t]
[t, t, t, t, t, t, t]
[t, t, t, t, t, t, t]
]
Domain of any variable in t:  0 10 15 22 32 34 47


Each team is supposed to be at home initially, and at the end of the double-robin tournament. Then, to compute the traveled distance by the team i for the first game or the last game, we use the following function:

def table_end(i):  # traveled distance for the first or last game of the ith team
return [(1, ANY, 0)] + [(0, j, distances[i][j]) for j in range(nTeams) if j != i]


This function returns a set (list) of 3-tuples where, for each tuple, the first value indicates if team i plays at home (1) or away(0), the second value is the opponent team, and the third value is the traveled distance. For example, if we print the table for the team 0, we can see that :

• playing at home against any team (*) requires traveling 0
• playing away against team 1 requires traveling 10
• playing away against team 2 requires traveling 15
• playing away against team 3 requires traveling 34
print(table_end(0))

[(1, *, 0), (0, 1, 10), (0, 2, 15), (0, 3, 34)]


For the other matches, we use some other tables, those returned by the following function:

def table(i):  # traveled distance for the a game that is not the first or last one of the ith team
return ([(1, 1, ANY, ANY, 0)] +
[(0, 1, j, ANY, distances[i][j]) for j in range(nTeams) if j != i] +
[(1, 0, ANY, j, distances[i][j]) for j in range(nTeams) if j != i] +
[(0, 0, j1, j2, distances[j1][j2]) for j1 in range(nTeams) for j2 in range(nTeams)
if different_values(i, j1, j2)])



This function returns a set (list) of 5-tuples where, for each tuple, the first value indicates if team i plays at home (1) or away(0) for the first match (of two consecutive matches), the second value indicates if team i plays at home (1) or away(0) for the second match, the third value is the opponent team for the first match, the fourth value is the opponent team for the second match, and the fifth value is the traveled distance. For example, if we print the table for the team 0, we can see that for any two consecutive matches involving team 0:

• playing at home twice against any team (*) requires traveling 0
• playing away against team 1 and then at home against any team requires traveling 10
• playing away against team 2 and then at home against any team requires traveling 15
• playing at home against any team and then away against team 1 requires traveling 10
• playing away against team 1 and then away against any team 2 requires traveling 22
• playing away against team 1 and then away against any team 3 requires traveling 32
print(table(0))

[(1, 1, *, *, 0), (0, 1, 1, *, 10), (0, 1, 2, *, 15), (0, 1, 3, *, 34), (1, 0, *, 1, 10), (1, 0, *, 2, 15), (1, 0, *, 3, 34), (0, 0, 1, 2, 22), (0, 0, 1, 3, 32), (0, 0, 2, 1, 22), (0, 0, 2, 3, 47), (0, 0, 3, 1, 32), (0, 0, 3, 2, 47)]


We can now post three groups of constraints Extension to be able to compute the distances traveled by all teams.

satisfy(
# handling traveling for the first game
[(h[i], o[i], t[i]) in table_end(i) for i in range(nTeams)],

# handling traveling for the last game
[(h[i][-1], o[i][-1], t[i][-1]) in table_end(i) for i in range(nTeams)],

# handling traveling for two successive games
[(h[i][k], h[i][k + 1], o[i][k], o[i][k + 1], t[i][k + 1]) in table(i)
for i in range(nTeams) for k in range(nRounds - 1)]
);


We can display the last posted constraint to control that the table is perfectly computed.

print(posted(-1,-1))

extension(list:[h, h, o, o, t], supports:(0,0,0,1,10)(0,0,0,2,15)(0,0,1,0,10)(0,0,1,2,22)(0,0,2,0,15)(0,0,2,1,22)(0,1,0,*,34)(0,1,1,*,32)(0,1,2,*,47)(1,0,*,0,34)(1,0,*,1,32)(1,0,*,2,47)(1,1,*,*,0))


We can run the solver.

if solve() is SAT:
for k in range(nRounds):
matches = [(i,o[i][k].value) for i in range(nTeams) if h[i][k].value == 1]
print(f"Matches at Round {k}: {matches}")
for i in range(nTeams):
print(f"Distance traveled by team {i}: {sum(t[i][k].value for k in range(nRounds))}")
print(f"Overall traveled distance: {sum(t[i][k].value for i in range(nTeams) for k in range(nRounds))}")

Matches at Round 0: [(1, 0), (3, 2)]
Matches at Round 1: [(0, 1), (2, 3)]
Matches at Round 2: [(2, 0), (3, 1)]
Matches at Round 3: [(0, 2), (1, 3)]
Matches at Round 4: [(2, 1), (3, 0)]
Matches at Round 5: [(0, 3), (1, 2)]
Distance traveled by team 0: 118
Distance traveled by team 1: 120
Distance traveled by team 2: 146
Distance traveled by team 3: 192
Overall traveled distance: 576


This is certainly not the cheapest solution in term of traveling.

## Minimizing Traveled Distances

The last thing to do is to post an objective function.

minimize(
# minimizing summed up traveled distance
Sum(t)
);


We can run the solver, with this optimization task. Note that we need to check that the status returned by the solver is now OPTIMUM.

if solve() is OPTIMUM:
for k in range(nRounds):
matches = [(i,o[i][k].value) for i in range(nTeams) if h[i][k].value == 1]
print(f"Matches at Round {k}: {matches}")
for i in range(nTeams):
print(f"Distance traveled by team {i}: {sum(t[i][k].value for k in range(nRounds))}")
print(f"Overall traveled distance: {bound()}")

Matches at Round 0: [(2, 0), (3, 1)]
Matches at Round 1: [(0, 3), (1, 2)]
Matches at Round 2: [(1, 0), (2, 3)]
Matches at Round 3: [(2, 1), (3, 0)]
Matches at Round 4: [(0, 1), (3, 2)]
Matches at Round 5: [(0, 2), (1, 3)]
Distance traveled by team 0: 106
Distance traveled by team 1: 111
Distance traveled by team 2: 125
Distance traveled by team 3: 128
Overall traveled distance: 517


Finally, we give below the model in one piece. Here the data is expected to be given by the user (in a command line).

from pycsp3 import *

distances = data
nTeams, nRounds = len(distances), len(distances) * 2 - 2
assert nTeams % 2 == 0, "An even number of teams is expected"
nConsecutiveGames = 2 if variant("a2") else 3  # used in one comment

def table(i):  # this is for the a game that is not the first or last one of the ith team
return ({(1, 1, ANY, ANY, 0)} |
{(0, 1, j, ANY, distances[i][j]) for j in range(nTeams) if j != i} |
{(1, 0, ANY, j, distances[i][j]) for j in range(nTeams) if j != i} |
{(0, 0, j1, j2, distances[j1][j2]) for j1 in range(nTeams) for j2 in range(nTeams)
if different_values(i, j1, j2)})

def table_end(i):  # this is for the first or last game of the ith team
return {(1, ANY, 0)} | {(0, j, distances[i][j]) for j in range(nTeams) if j != i}

def automaton():
qi, q01, q02, q03, q11, q12, q13 = states = "q", "q01", "q02", "q03", "q11", "q12", "q13"
trs = [(qi, 0, q01), (qi, 1, q11), (q01, 0, q02), (q01, 1, q11),
(q11, 0, q01), (q11, 1, q12), (q02, 1, q11), (q12, 0, q01)]
return Automaton(start=qi, transitions=trs, final=states[1:])

# o[i][k] is the opponent (team) of the ith team  at the kth round
o = VarArray(size=[nTeams, nRounds], dom=range(nTeams))

# h[i][k] is 1 iff the ith team plays at home at the kth round
h = VarArray(size=[nTeams, nRounds], dom={0, 1})

# t[i][k] is the travelled distance by the ith team at the kth round. An additional round is considered for returning at home.
t = VarArray(size=[nTeams, nRounds + 1], dom=distances)

satisfy(
# each team must play exactly two times against each other team
[Cardinality(o[i], occurrences={j: 2 for j in range(nTeams) if j != i}) for i in range(nTeams)],

# ensuring symmetry of games: if team i plays against j at round k, then team j plays against i at round k
[o[o[i][k]][k] == i for i in range(nTeams) for k in range(nRounds)],

# channeling the arrays o and h
[h[o[i][k]][k] != h[i][k] for i in range(nTeams) for k in range(nRounds)],

# playing against the same team must be done once at home and once away
[imply(o[i][k1] == o[i][k2], h[i][k1] != h[i][k2]) for i in range(nTeams)
for k1, k2 in combinations(range(nRounds), 2)],

# at most 'nConsecutiveGames' consecutive games at home, or consecutive games away
[h[i] in automaton() for i in range(nTeams)],

# handling travelling for the first game
[(h[i], o[i], t[i]) in table_end(i) for i in range(nTeams)],

# handling travelling for the last game
[(h[i][-1], o[i][-1], t[i][-1]) in table_end(i) for i in range(nTeams)],

# handling travelling for two successive games
[(h[i][k], h[i][k + 1], o[i][k], o[i][k + 1], t[i][k + 1]) in table(i)
for i in range(nTeams) for k in range(nRounds - 1)]
)

minimize(
# minimizing summed up travelled distance
Sum(t)
)