Scheduling games in a tournament

[rasmus0201]

Hello, please bear with me - I'm quite new to or-tools/constraint programming. :)

Problem Statement

I need to schedule a set of games (consisting of 2 teams each) on 1 or more fields in a tournament. I have already solved the 1st part of the problem by splitting a list of teams into groups, then pairing each team in the group with each other (a match) and then placing these matches in different fields where they need to be played. Teams might be assigned to play on more than 1 field. All matches have the same length time-wise.

Constraints

The part missing is ordering / scheduling the games such that:
a) Each match is played exactly once on the specified field.
b) No team can be double-scheduled - (meaning that if a match consisting of teams (A,B) were scheduled to play on field 1, in time slot 1, neither team A nor B can play another match on any other field at that same time slot (aka game).

Objective(s)

Further more I need an objective that optimizes how/when a team is playing, such that each particular team are as evenly distributed as possible throughout the day (this is regardless of which field the team plays on). This is to avoid having a team play all their e.g. 4 matches in the morning, and then have the rest of the day off. We need to optimize that the teams are playing at a somewhat evenly interval. This should also minimize the risk of a team playing 2 games in consecutive time slots, but if I'm mistaken and that's not implicitly incorporated in that objective I would also need another objective to try and minimize the risk of that happening.

I've tried come up with a solution for this for many days now, but I'm struggling with actually making it work. Here is the current code I have made:

Python code

#!/usr/bin/python3

from ortools.sat.python import cp_model
import argparse
import json
import pprint

pp = pprint.PrettyPrinter(indent=4)

# 1st dimension = field
# 2nd dimension = a match/game of 2 teams

# Simpler tournament
# team_games = [
#     [
#         [0, 1],
#         [0, 2],
#         [0, 3],

#         [5, 6],
#         [5, 7],
#         [7, 6],
#     ],
#     [
#         [4, 5],
#         [4, 6],
#         [4, 7],

#         [1, 2],
#         [1, 3],
#         [2, 3],
#     ],
# ]

# Advanced tournament
team_games = [
    [
        [0, 1],
        [0, 2],
        [0, 3],
        [3, 1],
        [2, 1],
        [3, 4],
        [2, 3],
        [1, 4],
        [2, 4],
        [0, 4],
        [5, 6],
        [5, 7],
        [5, 8],
        [9, 10],
        [11, 10],
        [9, 12],
        [11, 12],
        [9, 11],
        [12, 10]
    ],
    [
        [13, 14],
        [15, 14],
        [13, 16],
        [17, 16],
        [17, 14],
        [16, 14],
        [17, 13],
        [15, 17],
        [15, 16],
        [15, 13],
        [6, 7],
        [7, 8],
        [6, 8],
        [18, 19],
        [18, 20],
        [19, 20],
        [21, 18],
        [21, 19],
        [21, 20]
    ]
]

num_fields = len(team_games)
all_fields = range(num_fields)
all_teams = list(
    set([team for field in team_games for teams in field for team in teams]))

model = cp_model.CpModel()

# Make variable for each fields' slots's possible games
# games[(f, s, g)] = 1, that particular game g is to be played on field f in time slot s
max_num_games = 0
games = {}
for f in all_fields:
    num_games = len(team_games[f])
    all_game_slots = range(num_games)
    all_games = range(num_games)

    max_num_games = max(max_num_games, num_games)

    for s in all_game_slots:
        for g in all_games:
            games[(f, s, g)] = model.NewBoolVar(f'game_{f}_{s}_{g}')

    # Make sure the time slot s has exactly 1 game scheduled to be played.
    for s in all_game_slots:
        model.AddExactlyOne(games[(f, s, g)] for g in all_games)

    # Make sure the game g is assigned/scheduled to exactly 1 time slot.
    for g in all_games:
        model.AddExactlyOne(games[(f, s, g)] for s in all_game_slots)


# Create pairs of the same time-slots on the different fields.
# We should use it to make sure only a team is not assigned to that more than on 1 of those time slots (regardless of the field)
field_games_pairs = []
for field in all_fields:
    num_games = len(team_games[field])
    all_game_slots = range(num_games)
    all_games = range(num_games)

    for game_slot in all_game_slots:
        unique_teams = []
        for f in all_fields:
            if game_slot < len(team_games[f]):
                unique_teams.append((f, game_slot))

        if unique_teams not in field_games_pairs:
            field_games_pairs.append(unique_teams)

# Create a mapping between the team to the game/match they are playing in.
games_by_team = {}
for f in all_fields:
    for s, (home, away) in enumerate(team_games[f]):
        if not home in games_by_team:
            games_by_team[home] = []
        if not away in games_by_team:
            games_by_team[away] = []

        games_by_team[home].append((f, s))
        games_by_team[away].append((f, s))

# Create variables for each team,
# which links it together with the game's field+time-slots
teams_assigned_vars = {}
for t in all_teams:
    for f in all_fields:
        num_games = len(team_games[f])
        all_game_slots = range(num_games)
        all_games = range(num_games)

        for s in all_game_slots:
            team_assign_var = model.NewBoolVar(f'team_{t}_{f}_{s}')
            model.Add(team_assign_var == sum(
                games[(f, s, g)] for g in all_games))
            teams_assigned_vars[(t, f, s)] = team_assign_var

# Constrain team to maximally play 1 game in
# the possible (field, time slot) pairs
for pairs in field_games_pairs:
    for t in all_teams:
        possible_pairs = []
        for f, s in pairs:
            assigned_fields = set([t_f for t_f, t_s in games_by_team[t]])

            if len(assigned_fields) > 1 and f in assigned_fields:
                possible_pairs.append((f, s))

        if len(possible_pairs) == 0:
            continue

        # We are down here if we know that the team t, is supposed to play on multiple fields.
        team_restriction_vars = {}
        for f, s in possible_pairs:
            for g in range(len(team_games[f])):
                # Setup relationship between the specific game played on (f, s)
                # and the team assigned on (f, s)
                # If this is the case, v==True.
                v = model.NewBoolVar('v')
                model.AddMultiplicationEquality(
                    v,
                    [
                        games[(f, s, g)],
                        teams_assigned_vars[(t, f, s)]
                    ]
                )
                team_restriction_vars[(t, f, s)] = v

        # Based on the intermediary booleans, we can constrain those
        # to add most 1 is true for the particular team on the possible pairs of (f, s)
        model.AddAtMostOne(
            team_restriction_vars[(t, f, s)] for f, s in possible_pairs
        )

# Objective
# Minimize sum of each game index,
# this should try and equally divide all games into the slots/indexes
max_index_balancing_integers = []
for team, game_indexes in games_by_team.items():
    max_index_balancing_integers.append(
        sum([x + 1 for x in range(max_num_games - len(game_indexes), max_num_games)]))

max_index_balancing_integer = max(max_index_balancing_integers)
index_balancing_vars = []
for team, game_indexes in games_by_team.items():
    index_sum_balancing = []

    for f in all_fields:
        index_sum_var = model.NewIntVar(0, max_index_balancing_integer, 'v')
        sum_index = []
        for s in range(len(team_games[f])):
            for g in game_indexes:
                if (f, s, g) in games:
                    sum_index.append(games[(f, s, g)] * (1 + s))

        model.Add(index_sum_var == sum(sum_index))
        index_sum_balancing.append(index_sum_var)

    max_field_index_balancing_var = model.NewIntVar(
        0, max_index_balancing_integer, 'max_index_balancing')
    model.AddMaxEquality(max_field_index_balancing_var, index_sum_balancing)

model.Minimize(sum(index_balancing_vars))

solver = cp_model.CpSolver()
# solver.parameters.linearization_level = 1
status = solver.Solve(model)

if (status != cp_model.OPTIMAL) and (status != cp_model.FEASIBLE):
    exit()

result = {}
for f in all_fields:
    num_games = len(team_games[f])
    all_game_slots = range(num_games)
    all_games = range(num_games)

    if f not in result:
        result[f] = []

    for s in all_game_slots:
        for g in all_games:
            if solver.Value(games[(f, s, g)]) > 0:
                result[f].append(team_games[f][g])

pp.pprint(result)

Test run result

Result:

{   0: [   [9, 11],
           [12, 10],
           [0, 2],
           [0, 3],
           [3, 1],
           [2, 1],
           [3, 4],
           [2, 3],
           [1, 4],
           [2, 4],
           [0, 4],
           [5, 6],
           [5, 7],
           [5, 8],
           [9, 10],
           [11, 10],
           [9, 12],
           [0, 1],
           [11, 12]],
    1: [   [21, 20],
           [21, 19],
           [15, 14],
           [13, 16],
           [17, 16],
           [17, 14],
           [16, 14],
           [17, 13],
           [15, 17],
           [15, 16],
           [15, 13],
           [6, 7],
           [7, 8],
           [6, 8],
           [18, 19],
           [18, 20],
           [19, 20],
           [13, 14],
           [21, 18]]}

As you can see this produced at least one double-scheduled team (6) which is both assigned a time to play in f0 s11 and f1 s11. (match [5, 6] and [6, 7])

Please let me know if you have any suggestion to this a better way, as I'm not feeling like I'm getting good results. :)

Thank you for your helping me! :)

[Mizux]

recall me https://github.com/Mizux/tournament

[rasmus0201]

Hmm this looks like it will only schedule 1 "field" (e.g. a soccer field) of matches.

I have n number of fields I need to schedule the given matches. It is important that the predefined matches are scheduled on the particular fields from the input because it is coming from another part of the system which divides and possibly "splits" the groups so that the fields potential are maximized.

[Mizux]

can't you simply add a variable x[(f, s, t)] = 1 if team t play on field f on slot s
then you can express for each team t for each slot s: sum(x[(f, s, t)] with f in all_fields) <= 1

[lperron]

have you looked at: https://github.com/google/or-tools/blob/stable/examples/cpp/sports_scheduling_sat.cc

[rasmus0201]

Thank you, that was a really nice example. It helped a lot. I rewrote the entire code to match more with the example. Though I'm still not 100% sure I've got a perfect objective setup, but it seems to perform O.K.

If anyone is interested the entire solution is:

python code

#!/usr/bin/python3

from ortools.sat.python import cp_model
import numpy as np
import argparse
import json

def main(team_games=[]):
    model = cp_model.CpModel()

    teams_by_field = {}
    for field, matches in enumerate(team_games):
        teams = set()
        for home, away in matches:
            teams.add(home)
            teams.add(away)

        teams_by_field[field] = list(teams)

    teams_by_field_matches = {}
    for field, matches in enumerate(team_games):
        for match, teams in enumerate(matches):
            teams_by_field_matches[(field, match)] = teams

    match_by_team_pairs = {}
    for field, matches in enumerate(team_games):
        for match, teams in enumerate(matches):
            match_by_team_pairs[(teams[0], teams[1])] = match

    matches_by_teams = {}
    for field, matches in enumerate(team_games):
        for match, teams in enumerate(matches):
            if teams[0] not in matches_by_teams:
                matches_by_teams[teams[0]] = []
            if teams[1] not in matches_by_teams:
                matches_by_teams[teams[1]] = []

            matches_by_teams[teams[0]].append((field, match))
            matches_by_teams[teams[1]].append((field, match))

    field_by_slot = {}
    for field, matches in enumerate(team_games):
        for slot in range(len(matches)):
            if slot not in field_by_slot:
                field_by_slot[slot] = []

            field_by_slot[slot].append(field)

    game_slots = {}  # = 1 if match is to be scheduled on field f in slot s
    for field, matches in enumerate(team_games):
        for slot in range(len(matches)):
            for match, teams in enumerate(matches):
                game_slots[(field, slot, match)] = model.NewBoolVar(
                    f'game_slot_{field}_{slot}_{match}')


    # fixtures[d][i][j] is true if team i plays team j on field f in slot s
    fixtures = {}
    for field, matches in enumerate(team_games):
        for slot in range(len(matches)):
            for team in teams_by_field[field]:
                for opponent in teams_by_field[field]:
                    fixtures[(field, slot, team, opponent)] = model.NewBoolVar(
                        f'fixture_{field}_{slot}_{team}_{opponent}')


    team_assigned = {}  # if team is assigned to play in slot s on field f
    for field, matches in enumerate(team_games):
        for slot in range(len(matches)):
            for team in teams_by_field[field]:
                team_assigned[(field, slot, team)] = model.NewBoolVar(
                    f'team_assigned_{field}_{slot}_{team}')


    # If fixtures[(field, slot, team, opponent)] is True,
    # we know that team_assigned[(field, slot, team)] has to be True
    # and team_assigned[(field, slot, opponent)] is True
    for field, matches in enumerate(team_games):
        for slot in range(len(matches)):
            for team in teams_by_field[field]:
                for opponent in teams_by_field[field]:
                    model.AddImplication(
                        fixtures[(field, slot, team, opponent)],
                        team_assigned[(field, slot, team)]
                    )

                    model.AddImplication(
                        fixtures[(field, slot, team, opponent)],
                        team_assigned[(field, slot, opponent)]
                    )

    # If fixtures[(field, slot, team, opponent)] is True,
    # we know that game_slots[(field, slot, match)] should be True
    # where match is the index for the (team, opponent) match
    for field, matches in enumerate(team_games):
        for slot in range(len(matches)):
            for team in teams_by_field[field]:
                for opponent in teams_by_field[field]:
                    if not (team, opponent) in match_by_team_pairs:
                        continue

                    if not (field, slot, match_by_team_pairs[(team, opponent)]) in game_slots:
                        continue

                    model.AddImplication(
                        fixtures[(field, slot, team, opponent)],
                        game_slots[(
                            field, slot, match_by_team_pairs[(team, opponent)])]
                    )

    for field, matches in enumerate(team_games):
        for slot in range(len(matches)):
            for match, teams in enumerate(matches):
                model.AddImplication(
                    game_slots[(field, slot, match)],
                    team_assigned[(
                        field, slot, teams_by_field_matches[(field, match)][0])]
                )

                model.AddImplication(
                    game_slots[(field, slot, match)],
                    team_assigned[(
                        field, slot, teams_by_field_matches[(field, match)][1])]
                )

    # Constrain field time slot to hold exactly 1 match
    for field, matches in enumerate(team_games):
        for slot in range(len(matches)):
            model.AddExactlyOne(game_slots[(field, slot, match)]
                                for match, _ in enumerate(matches))

    # Constrain each match to be assigned to exactly one slot
    for field, matches in enumerate(team_games):
        for match, teams in enumerate(matches):
            model.AddExactlyOne(
                game_slots[(field, slot, match)] for slot in range(len(matches))
            )

    # Constrain a team cannot play in same time slot across fields
    for team, team_matches in matches_by_teams.items():
        for slot, fields in field_by_slot.items():
            restricted_slots = set()
            for field in fields:
                if (field, slot, team) in team_assigned:
                    restricted_slots.add((field, slot))

            if len(restricted_slots) <= 1:
                continue

            model.AddAtMostOne(team_assigned[(field, slot, team)] for field, slot in restricted_slots)

    # Constrain teams must play at least 1 game in the 1st half and 1 in the second half
    for team, team_matches in matches_by_teams.items():
        if len(team_matches) <= 1:
            continue

        first_half_matches = []
        second_half_matches = []
        for field, matches in enumerate(team_games):
            if team not in teams_by_field[field]:
                continue
            if len(matches) < 2:
                continue

            [first_half, second_half] = np.array_split(matches, 2)

            for match, teams in enumerate(first_half):
                if (field, match, team) not in team_assigned:
                    continue
                first_half_matches.append(team_assigned[(field, match, team)])

            for match, teams in enumerate(second_half):
                slot = match + len(first_half)
                if (field, slot, team) not in team_assigned:
                    continue
                second_half_matches.append(team_assigned[(field, slot, team)])

        if (len(first_half_matches) < 2) or (len(second_half_matches) < 2):
            continue

        model.AddAtLeastOne(first_half_matches)
        model.AddAtLeastOne(second_half_matches)

    # Constrain no team can play 3 consecutive slots
    for team, _ in matches_by_teams.items():
        for slot, fields in field_by_slot.items():
            restricted_slots = set()

            for field in fields:
                if (field, slot, team) not in team_assigned:
                    continue
                if (field, slot + 1, team) not in team_assigned:
                    continue
                if (field, slot + 2, team) not in team_assigned:
                    continue

                restricted_slots.add((field, slot))
                restricted_slots.add((field, slot + 1))
                restricted_slots.add((field, slot + 2))

            if len(restricted_slots) < 3:
                continue

            model.Add(sum(team_assigned[(field, slot, team)] for field, slot in restricted_slots) <= 2)

    # Try to minimize the summed indexes for each team's matches
    # This should - across teams - make sure of evenly distributing matches
    # so each team has their matches (somewhat) evenly distributed throughout the day
    index_balancing_vars = []
    for team, _ in matches_by_teams.items():
        slot_sum_balancing = []

        for field, matches in enumerate(team_games):
            for slot in range(len(matches)):
                for match, _ in enumerate(matches):
                    if (field, slot, team) not in team_assigned:
                        continue

                    v = model.NewBoolVar('v')
                    model.AddMultiplicationEquality(v, [
                        game_slots[(field, slot, match)],
                        team_assigned[(field, slot, team)]
                    ])

                    slot_sum_balancing.append(v)

        team_slot_sum_var = model.NewIntVar(0, 1_000, 'v')
        model.Add(team_slot_sum_var == sum(slot_sum_balancing))
        index_balancing_vars.append(team_slot_sum_var)

    model.Minimize(sum(index_balancing_vars))

    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 60
    status = solver.Solve(model)

    if (status != cp_model.OPTIMAL) and (status != cp_model.FEASIBLE):
        return None

    result = []
    for field, matches in enumerate(team_games):
        field_schedule = []
        for slot in range(len(matches)):
            for match, teams in enumerate(matches):
                if solver.Value(game_slots[(field, slot, match)]):
                    # Slot is the the index of the appended item.
                    field_schedule.append(team_games[field][match])
        result.append(field_schedule)

    return result

if __name__ == '__main__':
    parser = argparse.ArgumentParser(description='Get best possible schedule of games')

    parser.add_argument('-d', '--data',
                    help='A multi-array of fields, games which contains tuple of teams',
                    required=True)

    args = parser.parse_args()

    result = main(team_games=json.loads(args.data))

    json_object = json.dumps(result)
    print(json_object)

I even put in constraints regarding no team can play in 3 consecutive time slots and also each team needs to have at least 1 game in each half of the tournament (depending on total number of games).