0
$\begingroup$

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.linear_solver import pywraplp
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
$\endgroup$
8
  • $\begingroup$ You get 8 differences, one for each pair of teams. How do you want to combine those into a single overall objective function? Do you want to minimize the sum of the absolute values of the differences? sum of squares? the largest absolute difference? something else? $\endgroup$
    – D.W.
    Nov 24 at 5:05
  • $\begingroup$ I'm confused by your last paragraph. Everything else indicates that each person is assigned to one team, and there is only a single assignment that holds for all time. The last paragraph seems to really change the problem in a major way. I advise you to either revise the question to introduce all elements of the problem, or separate that out into a separate post. $\endgroup$
    – D.W.
    Nov 24 at 5:07
  • $\begingroup$ @D.W. Apologies for the confusion. Essentially I want to be able to solve the same problem 6 times in a row but ensure the additional constraints of never being on the same team as another individual twice, and never playing against another individual more than twice hold true for the iterations after the first. For your first question, yes: I want to minimize the sum of the absolute values of the differences. $\endgroup$
    – PlsHalp
    Nov 24 at 5:15
  • 1
    $\begingroup$ Thanks for your rapid reply! Please edit your question so it contains all relevant information and reads well for someone who encounters it for the first time. We don't want people to have to read the comments to understand what you're asking. Part of our mission is to build up an archive of high-quality questions and answers that will hopefully be useful to others in the future. Also, it's better to list all the constraints up front, rather than stating a problem and then having a critical requirement only appear in an addendum. $\endgroup$
    – D.W.
    Nov 24 at 6:16
  • $\begingroup$ @D.W. I've updated the entirety of the question. Apologies for the delay (was out of town for Turkey day). Please let me know if I need to make further edits/clarifications. $\endgroup$
    – PlsHalp
    2 days ago
0
$\begingroup$

Somehow I lost my login since I never fully signed up as PlsHalp... I was able to get this figured out via the following changes (thanks to the StackOverflow folk: https://stackoverflow.com/questions/70150911/ortools-minimizing-sum-of-pairwise-absdifference-assignment-scheduling-probl?noredirect=1#comment124018044_70150911)

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))]))
  1. 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.

Thank you, everyone, for your help!

New contributor
primegoat is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.