CP-SAT - Sports Scheduling

import { CpSat, setWorkerBridgeEnabled, type SatParameters } from 'or-tools-wasm/cp-sat';

type CpModelInput = {
  name: string;
  variables: Array<{ name: string; domain: number[] }>;
  constraints: Array<
    | { name?: string; linear: { vars: number[]; coeffs: number[]; domain: number[] } }
    | { name?: string; table: { vars: number[]; values: number[] } }
  >;
  objective?: { vars: number[]; coeffs: number[]; offset?: number; scaling_factor?: number };
};

function buildSportsScheduleModel(numTeams: number): CpModelInput {
  const numDays = 2 * numTeams - 2;
  const matchesPerHalf = numTeams - 1;
  const variables: CpModelInput['variables'] = [];
  const constraints: CpModelInput['constraints'] = [];
  const addVar = (name: string) => {
    const index = variables.length;
    variables.push({ name, domain: [0, 1] });
    return index;
  };
  const addSum = (name: string, vars: number[], domain: number[]) => {
    constraints.push({
      name,
      linear: { vars, coeffs: Array(vars.length).fill(1), domain },
    });
  };

  const fixture: number[][][] = [];
  for (let day = 0; day < numDays; ++day) {
    fixture[day] = [];
    for (let home = 0; home < numTeams; ++home) {
      fixture[day][home] = [];
      for (let away = 0; away < numTeams; ++away) {
        fixture[day][home][away] = home === away ? -1 : addVar(`d${day}_h${home}_a${away}`);
      }
    }
  }

  const atHome = Array.from({ length: numDays }, (_, day) =>
    Array.from({ length: numTeams }, (_, team) => addVar(`home_d${day}_t${team}`)),
  );

  for (let day = 0; day < numDays; ++day) {
    for (let team = 0; team < numTeams; ++team) {
      const plays: number[] = [];
      const homes: number[] = [];
      for (let other = 0; other < numTeams; ++other) {
        if (team === other) continue;
        plays.push(fixture[day][team][other], fixture[day][other][team]);
        homes.push(fixture[day][team][other]);
      }
      addSum(`plays_once_d${day}_t${team}`, plays, [1, 1]);
      constraints.push({
        name: `link_home_d${day}_t${team}`,
        linear: { vars: [...homes, atHome[day][team]], coeffs: [...homes.map(() => 1), -1], domain: [0, 0] },
      });
    }
  }

  for (let team = 0; team < numTeams; ++team) {
    for (let other = team + 1; other < numTeams; ++other) {
      const firstHalf: number[] = [];
      const secondHalf: number[] = [];
      for (let day = 0; day < matchesPerHalf; ++day) {
        firstHalf.push(fixture[day][team][other], fixture[day][other][team]);
        const secondDay = day + matchesPerHalf;
        secondHalf.push(fixture[secondDay][team][other], fixture[secondDay][other][team]);
      }
      addSum(`first_half_${team}_${other}`, firstHalf, [1, 1]);
      addSum(`second_half_${team}_${other}`, secondHalf, [1, 1]);
    }
  }

  const breaks: number[] = [];
  for (let team = 0; team < numTeams; ++team) {
    for (let day = 0; day < numDays - 1; ++day) {
      const breakVar = addVar(`break_t${team}_d${day}`);
      breaks.push(breakVar);
      constraints.push({
        table: {
          vars: [atHome[day][team], atHome[day + 1][team], breakVar],
          values: [0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1],
        },
      });
    }
  }

  return {
    name: 'sports_schedule',
    variables,
    constraints,
    objective: { vars: breaks, coeffs: Array(breaks.length).fill(1), offset: 0, scaling_factor: 1 },
  };
}

setWorkerBridgeEnabled(true);
const numTeams = 4;
const model = await CpSat.createModel(buildSportsScheduleModel(numTeams));
const validation = await CpSat.validate(model);
if (!validation.ok) throw new Error(validation.message);

const params: SatParameters = { numWorkers: 4, logSearchProgress: true };
const result = await CpSat.solve(model, params);
console.log(result.response?.objectiveValue, result.response?.solution);