ORTools Minimizing Sum of Pairwise Abs(Difference) - Assignment/Scheduling Problem

Question

This is an attempt at solving a scheduling problem. The goal would be to run it a number of times in sequence to get a weekly schedule for a sports league defined as follows:

1. There are 48 individuals, each ranked in skill sequentially.
2. Each individual is assigned to a Team. Teams are composed of 3 individuals.
3. The top 12 individuals cannot play against the bottom 12, by rank.
4. Individuals can only play with each other once.
5. Individuals cannot play against each other more than twice (the fewer the better).

*Individuals are labeled "Pods" in the code but are equivalent to an individual described above.

Below is the ortools code I'm trying to use to solve this. I think the hardest part is ensuring the objective function is correct, and that I constructed the constraints appropriately.

In the end, I have a matrix of columns (individuals) and rows (teams). There are 16 teams and I've constructed the objective function such that the odd rows play the following even row. The goal is to minimize the absolute value of the difference in the sum of the individuals' ranks on each team: minimize(sumOf(abs(home_i - away_i) for home/away in teams)). I'm not sure I correctly translated this sum of pairwise absolute differences into linear constraints.

I have a couple main questions:

1. It seems the cost always is 1176. Why is this happening? To me, it seems the optimal solution would be: SUM(ABS(team1 - team2)) for all teams, and since the teams are relatively close in min/max values, I would expect the cost to be far lower, especially considering I got a lot of abs(team1 - team2) == 0 deltas from the brute force solution for the initial run where no individuals have played with/against anyone else. (My solution for run one shown below)
2. If I try to run this sequentially (to take advantage of the played with/against constraints), I arrive at an infeasible solution on the second run. I created a pure brute-force solution which is on the 5th week now, and it hasn't had a problem satisfying these constraints. The major problem with the brute force solution is that it's now on about the 5-6th day of running and not done.
3. This code takes a long time to run! I put a 5 minute counter on it because it seemed to result in the same solution whether it ran for 5 minutes or 6 hours... and the solution it yielded was only after halting the problem 6 hours into its run. Did I misspecify something to cause it to run so long?
4. Does the code appear to do what I want from the description of the problem. I understand code review may be outside the scope of this question/answer format, but I figured I'd ask since a brief review may be required to help answer whether I've properly specified the objective function.

Thank you!

from ortools.sat.python import cp_model

from ultimate.classes import Pod, Team


def main(pods):

    # Declare pods
    # pods = [Pod(name=ix, rank=ix) for ix in range(1, 49)]
    # sorted_pods = sorted(self.pods, key=lambda x: x.rank, reverse=False)

    # Data
    num_top = 1
    num_bot = 1
    max_play_with = 1
    max_play_against = 2
    # TODO: padding for pod count not divisible by 3
    num_teams = int(len(pods) / 3)
    if len(pods) % 3 != 0:
        raise ValueError("Pods not divisible by 3.")

    # Model
    model = cp_model.CpModel()

    # Variables
    # x[i, j] is an array of 0-1 variables, which will be 1
    # if worker i is assigned to team j
    x = {}
    for ii in range(len(pods)):
        for jj in range(num_teams):
            x[ii, jj] = model.NewIntVar(0, 1, '')

    # Constraints
    # Each team is composed of three pods
    for jj in range(num_teams):
        model.Add(sum([x[ii, jj] for ii in range(len(pods))]) == 3)

    # Each pod can only be assigned once
    for ii in range(len(pods)):
        model.Add(sum([x[ii, jj] for jj in range(num_teams)]) == 1)

    # Top pods cannot play bottom pods
    for ii in range(num_top):
        for jj in range(len(pods) - num_bot, len(pods)):
            for kk in range(num_teams):
                # print(f'Adding constraint: x[{ii}, {kk}], x[{jj}, {kk}]')
                # Same team constraint
                model.Add(sum([x[ii, kk], x[jj, kk]]) <= 1)
                # Opponent constraint (only add when on an even team iteration)
                if kk % 2 == 0:
                    # print(f'Adding constraint: x[{ii}, {kk}, x[{jj}, {kk + 1}]')
                    model.Add(sum([x[ii, kk], x[jj, kk + 1]]) <= 1)
                    # print(f'Adding constraint: x[{ii}, {kk + 1}], x[{jj}, {kk}]')
                    model.Add(sum([x[ii, kk + 1], x[jj, kk]]) <= 1)

    # Pods cannot play with someone more than max_play_with
    for ii in range(len(pods)):
        # print(f'POD: {pod}')
        # print(f'Played with: {[key.rank for key in pod.played_with}]')
        for teammate in pods[ii].played_with:
            # Add the constraint
            if ii == 0:
                print(f'Pod: {pods[ii].rank}::: With: {teammate.rank}')
            for kk in range(num_teams):
                limit = max_play_with - pods[ii].played_with[teammate]['count']
                # print(f'WITH: x[{ii}, {kk}], x[{teammate.rank - 1, kk}]')
                model.Add(sum([x[ii, kk], x[teammate.rank - 1, kk]]) <= limit)

    # Pods cannot play against someone more than max_play_against
    for ii in range(len(pods)):
        # print(f'POD: {pod}')
        # print(f'Played against: {[key.rank for key in pod.played_against}]')
        for opponent in pods[ii].played_against:
            # Add the constraint
            if ii == 0:
                print(f'Pod: {pods[ii].rank}::: Against: {opponent.rank}')
            for kk in range(num_teams):
                limit = max_play_against - pods[ii].played_against[opponent]['count']
                # print(f'AGAINST: x[{ii}, {kk}], x[{opponent.rank - 1}, {kk}] <= {limit}]')
                model.Add(sum([x[ii, kk], x[opponent.rank - 1, kk]]) <= limit)

    # Objective
    homes = []
    aways = []
    for jj in range(num_teams):
        for ii in range(len(pods)):
            if jj % 2 == 0:
                homes.append(pods[ii].rank * x[ii, jj])
            else:
                aways.append(pods[ii].rank * x[ii, jj])

    # Pairwise sum of abs differences: need to minimize in obj fn
    # x_loss_abs = [model.NewIntVar(0, 1000000, 'x_loss_abs_%i' % i) for i in range(len(homes))]

    x_loss_abs = []
    for ih in range(len(homes)):
        # v = model.NewIntVar(-1000000, 1000000, 'v')  # Temporary variable
        # model.Add(v == (homes[ih] - aways[ih])
        # model.AddAbsEquality(x_loss_abs[ih], v)
        # Different attempt:
        v1 = model.NewIntVar(0, 1000, 'v1_%i' % ih)
        model.Add(homes[ih] - aways[ih] <= v1)
        model.Add(aways[ih] - homes[ih] <= v1)
        x_loss_abs.append(v1)

    # print('***matchups***')
    model.Minimize(sum(x_loss_abs))

    # Solve
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 60 * 5
    solver.parameters.num_search_workers = 8
    status = solver.Solve(model)

    # Print solution
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f'Total cost = {solver.ObjectiveValue()}\n')
        pod_teams = {}
        for jj in range(num_teams):
            for ii in range(len(pods)):
                # Test if x[ii, jj] is 1 (with tolerance for floating point arithmetic).
                # if x[ii, jj].solution_value() > 0.5:
                if solver.BooleanValue(x[ii, jj]):
                    if jj in pod_teams:
                        pod_teams[jj].append(pods[ii])
                    else:
                        pod_teams[jj] = [pods[ii]]
        teams = []
        for tt in range(len(pod_teams)):
            print(f'Team{tt}: {sum([pod.rank for pod in pod_teams[tt]])} Pods: {[pod.rank for pod in pod_teams[tt]]}')
            team = Team(pods=pod_teams[tt])
            teams.append(team)
        return teams

    elif status == cp_model.INFEASIBLE:
        print('INFEASIBLE SOLUTION')
        return None

    else:
        print('NO SOLUTION')
        print(dir(cp_model))
        print(status)
        return None


if __name__ == '__main__':
    pods = [Pod(name=ix, rank=ix) for ix in range(1, 49)]
    main(pods)


class Pod:
    is_bottom = False
    is_top = False

    def __init__(self, name, rank):
        self.name = name
        self.rank = rank
        self.played_with = {}
        self.played_against = {}

    def play_with(self, pod):
        if pod in self.played_with:
            self.played_with[pod]['count'] += 1
            # self.played_with (things like week, etc. could go here)
        else:
            self.played_with[pod] = {'count': 1}

    def play_against(self, pod):
        if pod in self.played_against:
            self.played_against[pod]['count'] += 1
        else:
            self.played_against[pod] = {'count': 1}

    def __str__(self):
        return str(self.name)

Yields after one run: (and I'm not sure why... I would have thought the cost would yield: Sum(abs(team0 - team1) + ... + abs(team14 - team15)) == (37 + 31 + 11 + 3 + 19 + 3 + 9 + 1) == 114)

Total cost = 1176.0

Team0: 82 Pods: [1, 39, 42]
Team1: 119 Pods: [38, 40, 41]
Team2: 72 Pods: [2, 33, 37]
Team3: 103 Pods: [32, 35, 36]
Team4: 76 Pods: [18, 27, 31]
Team5: 87 Pods: [28, 29, 30]
Team6: 72 Pods: [21, 25, 26]
Team7: 69 Pods: [22, 23, 24]
Team8: 70 Pods: [16, 20, 34]
Team9: 51 Pods: [15, 17, 19]
Team10: 36 Pods: [9, 13, 14]
Team11: 33 Pods: [10, 11, 12]
Team12: 141 Pods: [46, 47, 48]
Team13: 132 Pods: [43, 44, 45]
Team14: 16 Pods: [3, 5, 8]
Team15: 17 Pods: [4, 6, 7]

Yields (errors) after two consecutive runs where the first run's output is cached and the Individuals' teammates/opponents updated: generating first schedule of day... Total cost = 1176.0

Team0: 82 Pods: [1, 39, 42]
Team1: 119 Pods: [38, 40, 41]
Team2: 72 Pods: [2, 33, 37]
Team3: 103 Pods: [32, 35, 36]
Team4: 76 Pods: [18, 27, 31]
Team5: 87 Pods: [28, 29, 30]
Team6: 72 Pods: [21, 25, 26]
Team7: 69 Pods: [22, 23, 24]
Team8: 70 Pods: [16, 20, 34]
Team9: 51 Pods: [15, 17, 19]
Team10: 36 Pods: [9, 13, 14]
Team11: 33 Pods: [10, 11, 12]
Team12: 141 Pods: [46, 47, 48]
Team13: 132 Pods: [43, 44, 45]
Team14: 16 Pods: [3, 5, 8]
Team15: 17 Pods: [4, 6, 7]
****len(teams): 16
1:0:0:::
generating first schedule of day...
Pod: 1::: With: 39
Pod: 1::: With: 42
Pod: 1::: Against: 38
Pod: 1::: Against: 40
Pod: 1::: Against: 41
INFEASIBLE SOLUTION

Answer 1

Per @ChristopherHamkins excellent suggestion in the comments, the issue was isolated to being two things:

1. I incorrectly specified the team vs. team constraint and didn't properly sum up the pods in a team. The code has been corrected to the following:

# Objective
homes = []
aways = []
for jj in range(num_teams):
    if jj % 2 == 0:
        homes.append(sum([pods[ii].rank * x[ii, jj] for ii in range(len(pods))]))
    else:
        aways.append(sum([pods[ii].rank * x[ii, jj] for ii in range(len(pods))]))

2. The limit specification for the played_with and played_against specifications was wrongly setting the sums to <= 0 when it should have been <= 1. That is now fixed:

# Pods cannot play with someone more than max_play_with
for ii in range(len(pods)):
    # print(f'POD: {pod}')
    # print(f'Played with: {[key.rank for key in pod.played_with}]')
    for teammate in pods[ii].played_with:
        # Add the constraint
        if ii == 0:
            print(f'Pod: {pods[ii].rank}::: With: {teammate.rank}')
        for kk in range(num_teams):
            limit = 2 if max_play_with - pods[ii].played_with[teammate]['count'] > 0 else 1
            if limit == 0:
                raise ValueError(
                    f"LIMIT IS 0:\npod: {pods[ii]}\nConstraint:"
                    f'WITH: x[{ii}, {kk}], x[{teammate.rank - 1, kk}]'
                )
            # print(f'WITH: x[{ii}, {kk}], x[{teammate.rank - 1, kk}]')
            model.Add(sum([x[ii, kk], x[teammate.rank - 1, kk]]) <= limit)

# Pods cannot play against someone more than max_play_against
for ii in range(len(pods)):
    # print(f'POD: {pod}')
    # print(f'Played against: {[key.rank for key in pod.played_against}]')
    for opponent in pods[ii].played_against:
        # Add the constraint
        if ii == 0:
            print(f'Pod: {pods[ii].rank}::: Against: {opponent.rank}')
        for kk in range(num_teams):
            limit = 2 if max_play_with - pods[ii].played_against[opponent]['count'] > 0 else 1
            # print(f'AGAINST: x[{ii}, {kk}], x[{opponent.rank - 1}, {kk}] <= {limit}]')
            model.Add(sum([x[ii, kk], x[opponent.rank - 1, kk]]) <= limit)

The code now executes properly without error. I will analyze the results to ensure they were appropriately produced when I'm done working today, but the crux of the INFEASIBLE SOLUTION issue was solved.