Link Search Menu Expand Document
PyCSP3
Models & Data GitHub XCSP3 About
Documentation
XCSP web site is provided by CRIL
This site uses Just the Docs, a documentation theme for Jekyll.
download notebook
CSP  medium 

Problem Sport Scheduling

From CSPLib (Problem 26): The problem is to schedule a tournament of $n$ teams over $n-1$ weeks, with each week divided into $n/2$ periods, and each period divided into two slots indicating the two involved teams (for example, one playing at home, and the other away). A tournament must satisfy the following three conditions:

  • every team plays every other team.
  • every team plays once a week;
  • every team plays at most twice in the same period over the tournament;

Sports Scheduling. Image from commons.wikimedia.org Carter All-Interval

To build a CSP (Constraint Satisfaction Problem) model, we need first to import the library PyCSP$^3$:

from pycsp3 import *

Then, we need some data. Actually, we just need an (even) integer $n$. For example, the value 6.

nTeams = 6
nWeeks = nTeams -1
nPeriods = nTeams // 2
nMatches = (nTeams - 1) * nTeams // 2

We display the value fo the constants, to control them:

print("Number of periods: ", nPeriods)
print("Number of matches: ", nMatches)

Number of periods:  3
Number of matches:  15

Is is interesting to associate a distinct number to each possible match between two teams. We define this function:

def match_number(t1, t2):
    return nMatches - ((nTeams - t1) * (nTeams - t1 - 1)) // 2 + (t2 - t1 - 1)

We then compute a table containing information (3-tuples) about all possible matches.

T = [(t1, t2, match_number(t1,t2)) for t1, t2 in combinations(range(nTeams), 2)]

We print the table to control it.

print(T)

[(0, 1, 0), (0, 2, 1), (0, 3, 2), (0, 4, 3), (0, 5, 4), (1, 2, 5), (1, 3, 6), (1, 4, 7), (1, 5, 8), (2, 3, 9), (2, 4, 10), (2, 5, 11), (3, 4, 12), (3, 5, 13), (4, 5, 14)]

Note that we do not pay attention to the fact that one team is playing at home and the other away. By construction, any match with number k corresponds to a 3 -tuple (i,j,k) with systematically $i < j$. So, what is recorded in the table is basically the identification of the two teams involved in any match (but not the site where they play).

We gently start our CSP model with a two-dimensional array $m$ of $5 \times 3$ variables. This will allow us to represent the number of the match to be played at any week w and any period p.

# m[w][p] is the number of the match at week w and period p
m = VarArray(size=[nWeeks, nPeriods], dom=range(nMatches))

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

print("Array of variable m: ", m)
print("Domain of any variable in m: ", m[0][0].dom)

Array of variable m:  [
  [m[0][0], m[0][1], m[0][2]]
  [m[1][0], m[1][1], m[1][2]]
  [m[2][0], m[2][1], m[2][2]]
  [m[3][0], m[3][1], m[3][2]]
  [m[4][0], m[4][1], m[4][2]]
]
Domain of any variable in m:  0..14

Concerning the constraints, we first post a constraint AllDifferent.

satisfy(
    # all matches are different (no team can play twice against another team)
    AllDifferent(m)
);

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

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

[
  [0, 1, 2]
  [3, 4, 5]
  [6, 7, 8]
  [9, 10, 11]
  [12, 13, 14]
]

In that “solution”, one can see that the first condition (every team plays every other team) in the statement of the problem is respected, but not the others (when observing the teams playing each week by looking at the correspondances given in the table).

Actually, we need to identify the teams involved in the matches. This is why we introduce 2 two-dimensional arrays $x$ and $y$ of $5 \times 3$ variables.

# x[w][p] is the first team for the match at week w and period p
x = VarArray(size=[nWeeks, nPeriods], dom=range(nTeams))

# y[w][p] is the second team for the match at week w and period p
y = VarArray(size=[nWeeks, nPeriods], dom=range(nTeams))

To make the connection between the matches and the teams, we post a group of constraints Extension.

satisfy(
    # linking variables through ternary table constraints
    (x[w][p], y[w][p], m[w][p]) in T for w in range(nWeeks) for p in range(nPeriods)
);

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. Here, we just display the 3 last posted constraints.

print(posted()[-3:])

extension(list:[x[4][0], y[4][0], m[4][0]], supports:(0,1,0)(0,2,1)(0,3,2)(0,4,3)(0,5,4)(1,2,5)(1,3,6)(1,4,7)(1,5,8)(2,3,9)(2,4,10)(2,5,11)(3,4,12)(3,5,13)(4,5,14))
extension(list:[x[4][1], y[4][1], m[4][1]], supports:(0,1,0)(0,2,1)(0,3,2)(0,4,3)(0,5,4)(1,2,5)(1,3,6)(1,4,7)(1,5,8)(2,3,9)(2,4,10)(2,5,11)(3,4,12)(3,5,13)(4,5,14))
extension(list:[x[4][2], y[4][2], m[4][2]], supports:(0,1,0)(0,2,1)(0,3,2)(0,4,3)(0,5,4)(1,2,5)(1,3,6)(1,4,7)(1,5,8)(2,3,9)(2,4,10)(2,5,11)(3,4,12)(3,5,13)(4,5,14))

We can run again the solver.

if solve() is SAT:
    print(values(m))
    for w in range(nWeeks):
        print(f"Matches at Week {w}: {[(x[w][p].value,y[w][p].value) for p in range(nPeriods)]}")
    

[
  [0, 1, 2]
  [3, 4, 5]
  [6, 7, 8]
  [9, 10, 11]
  [12, 13, 14]
]
Matches at Week 0: [(0, 1), (0, 2), (0, 3)]
Matches at Week 1: [(0, 4), (0, 5), (1, 2)]
Matches at Week 2: [(1, 3), (1, 4), (1, 5)]
Matches at Week 3: [(2, 3), (2, 4), (2, 5)]
Matches at Week 4: [(3, 4), (3, 5), (4, 5)]

The solution is always the same, but we are now in a position to post constraints so as to respect the second and third conditions in the statement of the problem.

We start with the second condition in the statement of the problem:

satisfy(
    # each week, all teams are different (each team plays each week)
    AllDifferent(x[w] + y[w]) for w in range(nWeeks)
);

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

print(posted(-1))

allDifferent(list:[x[0][0], x[0][1], x[0][2], y[0][0], y[0][1], y[0][2]])
allDifferent(list:[x[1][0], x[1][1], x[1][2], y[1][0], y[1][1], y[1][2]])
allDifferent(list:[x[2][0], x[2][1], x[2][2], y[2][0], y[2][1], y[2][2]])
allDifferent(list:[x[3][0], x[3][1], x[3][2], y[3][0], y[3][1], y[3][2]])
allDifferent(list:[x[4][0], x[4][1], x[4][2], y[4][0], y[4][1], y[4][2]])

We can run the solver.

if solve() is SAT:
    for w in range(nWeeks):
        print(f"Matches at Week {w}: {[(x[w][p].value,y[w][p].value) for p in range(nPeriods)]}")

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

This is better.

Finally, we impose the third condition in the statement of the problem by posting a group of constraints Cardinality.

satisfy(
    # each team plays at most two times in each period
    Cardinality(x[:, p] + y[:, p], occurrences={t: range(1, 3) for t in range(nTeams)}) for p in range(nPeriods)
);

We can control the posted constraints.

print(posted(-1))

cardinality(list:[x[0][0], x[1][0], x[2][0], x[3][0], x[4][0], y[0][0], y[1][0], y[2][0], y[3][0], y[4][0]], values:[0, 1, 2, 3, 4, 5], occurs:[1..2, 1..2, 1..2, 1..2, 1..2, 1..2])
cardinality(list:[x[0][1], x[1][1], x[2][1], x[3][1], x[4][1], y[0][1], y[1][1], y[2][1], y[3][1], y[4][1]], values:[0, 1, 2, 3, 4, 5], occurs:[1..2, 1..2, 1..2, 1..2, 1..2, 1..2])
cardinality(list:[x[0][2], x[1][2], x[2][2], x[3][2], x[4][2], y[0][2], y[1][2], y[2][2], y[3][2], y[4][2]], values:[0, 1, 2, 3, 4, 5], occurs:[1..2, 1..2, 1..2, 1..2, 1..2, 1..2])

We can run the solver.

if solve() is SAT:
    for w in range(nWeeks):
        print(f"Matches at Week {w}: {[(x[w][p].value,y[w][p].value) for p in range(nPeriods)]}")

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

Athough not shown here, it is possible to add some symmetry-breaking constraints, and also to reason with a dummy week (to make stronger the constraints Cardinality).

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 *

nTeams = data or 8
nWeeks, nPeriods, nMatches = nTeams - 1, nTeams // 2, (nTeams - 1) * nTeams // 2


def match_number(t1, t2):
    return nMatches - ((nTeams - t1) * (nTeams - t1 - 1)) // 2 + (t2 - t1 - 1)


T = {(t1, t2, match_number(t1, t2)) for t1, t2 in combinations(range(nTeams), 2)}

# m[w][p] is the number of the match at week w and period p
m = VarArray(size=[nWeeks, nPeriods], dom=range(nMatches))

# x[w][p] is the first team for the match at week w and period p
x = VarArray(size=[nWeeks, nPeriods], dom=range(nTeams))

# y[w][p] is the second team for the match at week w and period p
y = VarArray(size=[nWeeks, nPeriods], dom=range(nTeams))

satisfy(
    # all matches are different (no team can play twice against another team)
    AllDifferent(m),

    # linking variables through ternary table constraints
    [(x[w][p], y[w][p], m[w][p]) in T for w in range(nWeeks) for p in range(nPeriods)],

    # each week, all teams are different (each team plays each week)
    [AllDifferent(x[w] + y[w]) for w in range(nWeeks)],

    # each team plays at most two times in each period
    [Cardinality(x[:, p] + y[:, p], occurrences={t: range(1, 3) for t in range(nTeams)}) for p in range(nPeriods)]
)