Round robin scheduling with CP-SAT from Google OR tools

Question

I am creating round robin tournament fixtures with CP-SAT from google OR tools in python.

Problem: There are multiple teams about 150 split in to different groups and divisions in a league. The teams share ground and ground also has constraint about some days it will not be available. I need to make a fairly allocated round robin groups where teams play home and away leg matches. Teams do not want to plan more than 1 or 2 home matches consecutively. When possible team wants to finish playing against all oppositions (with combination of home/away) before playing each other again.

Solution:

Currently I using, boolean variables g_h_o_d (ground_home_opposition_date). And add constraints such as:

• No two teams plays on the same ground on same date
• All home teams play exactly one match against all oppositions
• Team play atmost one match on a given date.

Result: This works well, but the result is not distributed well enough as in I could have two team (x and y) playing against each in two consecutive days or teams playing all home matches before starting their away. Any clue, what constraints I can add to prevent this?

from ortools.sat.python import cp_model
import logging
import sys
import math

def match_date(n):  
    return n[-1]    

class SolutionPrinter(cp_model.CpSolverSolutionCallback):
  """Print intermediate solutions."""

  def __init__(self, matches):
      cp_model.CpSolverSolutionCallback.__init__(self)
      self._matches = matches

  def on_solution_callback(self):
      result = []
      match_count = 0
      for match in self._matches:
        h,o,d = match[0],match[1],match[2]
        if self.Value(self._matches[(h,o,d)]):
          match_count += 1
          result.append(match)
      logging.info('Match Count: %i' % match_count)
      for match in sorted(result, key=match_date):
        print (f"{match[2]}: {match[0]} X {match[1]}")
      self.StopSearch()

def teams_on_a_day_constraint(model, matches):
  # team plays atmost one match in a day
  # regardless of ground or opposition 
  constraints = {}
  for match in matches:
    h,o,d = match[0],match[1],match[2]
    try:
      constraints[f"{h}_{d}"].append(matches[h,o,d])
    except KeyError:
      constraints[f"{h}_{d}"] = []
      constraints[f"{h}_{d}"].append(matches[h,o,d])

    try:
      constraints[f"{o}_{d}"].append(matches[h,o,d])
    except KeyError:
      constraints[f"{o}_{d}"] = []
      constraints[f"{o}_{d}"].append(matches[h,o,d])

  for constraint in constraints.values():
    model.AddAtMostOne(constraint)

def home_opposition_constraint(model, matches):
    logging.debug ("setting constraints home-opposition constraint")
    # all teams play exactly one match against all oppositions
    # regardless of ground or days
    constraints = {}
    for match in matches:
      h,o,d = match[0],match[1],match[2]
      try:
        constraints[f"{h}_{o}"].append(matches[h,o,d])
      except KeyError:
        constraints[f"{h}_{o}"] = []
        constraints[f"{h}_{o}"].append(matches[h,o,d])
    for constraint in constraints.values():
      model.AddExactlyOne(constraint)


if __name__ == '__main__':
  logging.basicConfig(stream=sys.stdout, level=logging.DEBUG)
  nb_teams = 4
  home_teams = [f"Team_{x+1}" for x in range(nb_teams)]
  oppo_teams = [f"Team_{x+1}" for x in range(nb_teams)]
  # for 3 and teams, date neeed is 6
  nb_dates_needed = (math.ceil(nb_teams/2)*2*2) -2
  dates = [f"Date_{x+1}" for x in range(nb_dates_needed)]

  # Creates the model.
  model = cp_model.CpModel()
  
  # create variables
  matches = {}
  for h in home_teams:
    for o in oppo_teams:
      for d in dates:
        if h == o:
          continue
        matches[h,o,d] = model.NewBoolVar(f'match_h{h}_o{o}d_{d}')  

  # constraints
  home_opposition_constraint(model, matches)
  teams_on_a_day_constraint(model, matches)

  logging.debug ("solve")
  # Creates the model.
  solver = cp_model.CpSolver()
  solution_printer = SolutionPrinter(matches)
  status = solver.Solve(model, solution_printer)

Answer 1

In the sports_scheduling example, we force the scheduling to be separated in 2 half seasons.

You could also add rolling constraints for each team saying that the sum over X fixtures of the 2 booleans corresponding to the same opponent must be <= 1.