Constraint Satisfaction Problem for round-robin pairings and odd number of teams

Question

I am trying to model a CSP to generate round-robin pairings/matchups in a sports league using Google OR-Tools CP-SAT Solver.

The tool will take two parameters: number of teams and number of games each team should play. The expected result is a schedule where teams are paired "evenly".

The problem is modelled as a 3-dimensional structure with boolean values: if pairings[g][i][j] means team i plays team j in their game g. Note that this also implies home and away positions. This is how the model is created:

# team i plays team j on game g
for g in self.games:
    self.pairings.append([])
    for i in self.teams:
        self.pairings[g].append([])
        for j in self.teams:
            self.pairings[g][i].append(self.model.NewBoolVar('{}v{} [#{}]'.format(i, j, g + 1)))
            if i == j:
                # team cannot play self
                self.model.Add(self.pairings[g][i][j] == 0)

It works great, except when the number of teams is odd.

There are several constraints enforcing the following and they all seem to work in all cases (even or odd number of teams; edit: except when both number of teams and games are odd):

total number of games each team plays. (Not necessary but helps reinforce the model)
round-robin constraint enforces that every "round" each team play every other. For example if we have 5 teams and 10 games, games are "split" in 4/4/2 rounds and the constraint ensures that every team plays every other exactly once in the first two rounds and once, at most, in the last one (since it's not a perfect round).
number of match-ups constraint enforces the number of times every team play each other. (Not necessary as it's indirectly introduced by the round-robin constraint but helps reinforce the model)
number of home/away constraint enforces that teams get a balanced number of home and away number of games, for example 5 home and 5 away if they play 10 games, or 3 home and 4 away if they play 7 games.
maximum number of consecutive home/away games constraint aims at a balanced home/away spread by enforcing that there cannot be more than 2 consecutive home or consecutive away games. I tried having this as no more than 1 consecutive sequence but apparently this is mathematically impossible? The model would always be infeasable.

There is one more key constraint which is the one I pinned as problematic with odd number of teams:

one opponent constraint ensures that for each game, team i plays team j exactly once, either as home or as away.

This is how it's modelled:

# ensure that a game occurs: each game, team i plays team j exactly once as i vs j or as j vs i
for g in self.games:
    for i in self.teams:
        opponents = []
        for j in self.teams:
            if i == j:
                continue
            opponents.append(self.pairings[g][i][j])
            opponents.append(self.pairings[g][j][i])
        self.model.Add(sum(opponents) == 1)

This constraint make schedules with odd number of teams infeasable. When turned off, a solution is found but I get "unbalanced" schedules, such as:

Schedule (6 teams; 5 games):
Game 1: (0, 5) (1, 5) (2, 4) (4, 1)
Game 2: (3, 2) (4, 0)
Game 3: (0, 3) (1, 0)
Game 4: (0, 2) (3, 5)
Game 5: (2, 1) (3, 1) (4, 3) (5, 2) (5, 4)

And it also messes up even number of team schedules:

Schedule (8 teams; 8 games):
Game 1: (0, 2) (4, 5) (7, 3)
Game 2: (0, 7) (1, 0) (2, 5) (2, 6) (3, 4) (4, 6) (5, 7) (6, 0) (7, 1)
Game 3: (3, 1)
Game 4: (0, 3) (1, 4) (7, 2)
Game 5: (3, 5) (5, 6) (6, 1) (6, 7)
Game 6: (1, 5) (2, 4) (3, 6) (4, 0) (4, 7) (5, 0)
Game 7: (1, 2) (2, 3)
Game 8: (0, 3) (5, 4) (6, 2) (7, 1)

That otherwise would look nice and clean like this:

Schedule (8 teams; 8 games):
Game 1: (1, 0) (5, 3) (6, 4) (7, 2)
Game 2: (0, 5) (2, 1) (3, 6) (4, 7)
Game 3: (0, 2) (4, 3) (5, 6) (7, 1)
Game 4: (1, 5) (2, 4) (3, 7) (6, 0)
Game 5: (0, 3) (1, 4) (2, 6) (5, 7)
Game 6: (3, 2) (4, 5) (6, 1) (7, 0)
Game 7: (0, 4) (2, 5) (3, 1) (6, 7)
Game 8: (1, 6) (4, 3) (5, 0) (7, 2)

Can you help me understand why this isn't working with odd number of teams? Is this a inherent mathematical issue? Or there is a way around it?

The only solution I've thought of is adding a "bye" team and an extra game for each team, but that messes up the whole round-robin and home/away balance since we're adding a team and games that aren't real.

I also tried changing the one opponent constraint to self.model.Add(sum(opponents) <= 1) since with odd number of teams a game might not happen since it's a bye, but it also comes up as infeasable.

PS: if you are interested in the entire code I can link a gist. It's under 200 lines of code.

edit: new development: if the number of teams is odd and number of games is also odd, the schedule is unfeasable even when all constraints are turned off except the total number of games constraint, which is implemented as follows:

for i in self.teams:
    games = []
    for g in self.games:
        for j in self.teams:
            if i == j:
                continue
            games.append(self.pairings[g][i][j])
            games.append(self.pairings[g][j][i])
    self.model.Add(sum(games) == self.num_games)

Which I guess makes sense because if you try pairing teams you always end up with 1 game short or extra. Is this related to the main issue? How do I deal with this?

Constraint Satisfaction Problem for round-robin pairings and odd number of teams

0 Answers