pulp scheduling program needs more efficient problem definition

Question

I wrote a program with PuLP to optimize the schedule for my league. There are 16 players and 7 rounds. Each round consists of 4 games. Each game is two players vs. two players. Each player has a rating. The objective is to minimize the absolute rating difference between the teams. The constraints are that every player:

must play 7 rounds
can only play 1 game per round
can only be partnered with another player 0 or 1 times
can only be opponent of another player 0, 1, or 2 times

The code below works, but takes several minutes to run. I am an experienced python programmer but a relative novice at linear programming so I am not sure if the problem can be defined more efficiently in order to speed up the solution time.

import pulp
import numpy as np


p = np.array(['Joe', 'Tom', 'Sam', 'Bill', 'Fred', 'John', 'Wex', 'Chip',
            'Mike', 'Jeff', 'Steve', 'Kumar', 'Connor', 'Matt', 'Peter', 'Cindy'])
r = np.array([5.0, 4.2, 4.3, 5.1, 4.4, 3.7, 3.8, 4.6, 3.2, 3.6, 3.8, 4.7, 4.3, 4.6, 4.2, 3.4])
s = dict(zip(p, r))

n_games = 7

# calculate team combinations
team_combos = list(pulp.combination(p, 2))

# calculate game combinations
# each item is a 3-tuple of tuple(team1), tuple(team2), game_number
game_combos = []
for t in team_combos:
    for tt in team_combos:
        if t[0] in tt or t[1] in tt:
            continue
        for game_number in np.arange(n_games) + 1:
            game_combos.append((t, tt, game_number))

# calculate game score differential
game_scores = {}
for gc in game_combos:
    p1, p2 = gc[0]
    p3, p4 = gc[1]
    game_scores[(gc[0], gc[1])] = np.abs((s[p1] + s[p2]) - (s[p3] + s[p4]))

# decision variables
gcvars = pulp.LpVariable.dicts('gc_decvar', game_combos, cat=pulp.LpBinary)

# create problem
# minimize game scores subject to constraints
prob = pulp.LpProblem("PBOpt", pulp.LpMinimize)

# objective function
# minimize difference between team scores
prob += pulp.lpSum([gcvars[gc] * game_scores[(gc[0], gc[1])] for gc in game_combos])

# constraints
# each player must have n_games games
for player in p:
    prob += pulp.lpSum([v for k, v in gcvars.items()
                    if (player in k[0] or player in k[1])]) == n_games

# each player has 1 game per game_number
for player in p:
    for game_number in np.arange(1, n_games + 1):
        prob += pulp.lpSum([v for k, v in gcvars.items()
                            if (player in k[0] or player in k[1]) and
                            k[2] == game_number]) == 1

# do not play with a player more than once
# do not play against a player more than twice
for player in p:
    for pplayer in p:
        if player == pplayer:
            continue
        prob += pulp.lpSum([v for k, v in gcvars.items()
                            if (player in k[0] and pplayer in k[0]) or
                            (player in k[1] and pplayer in k[1])]) <= 1
        prob += pulp.lpSum([v for k, v in gcvars.items()
                            if (player in k[0] and pplayer in k[1]) or
                            (player in k[1] and pplayer in k[0])]) <= 2

# solve and print solution
prob.solve()
print([k for k, v in gcvars.items() if v.varValue == 1])

AirSquid AirSquid · Accepted Answer · 2021-05-19T23:33:31

Good news/Bad news...

There is still a little meat left on the bone there that you could trim. You have several loops that are generating redundant elements. The bad news is that the solver usually can detect these and will weed them out, so you may not get much acceleration by trimming them.

3 things...

Your constraint that a player must have n_games is redundant because your next constraint forces them to have a game in each round
When you are creating your player - pplayer constraints, you are creating many duplicates because you are implicitly ordering p and pp. If the set P has 16 players, then the nested loop will create p*(p-1) constraints of each type, when ignoring p=pp. However, note that there are only C(16,2) logical constraints which is p*(p-1)/2.
You are doing similar thing when creating your set of legal games because you are implicitly ordering the legal teams.

Below is a tweaked version of your program.... It is still churning on my machine, so I don't know if any time will be saved. Your other "easy" options are to tinker with an optimality gap or a timeout.

I'll stew on this a bit more... but I'm not sure if there is another novel approach to this.

import pulp
import numpy as np


p = np.array(['Joe', 'Tom', 'Sam', 'Bill', 'Fred', 'John', 'Wex', 'Chip',
            'Mike', 'Jeff', 'Steve', 'Kumar', 'Connor', 'Matt', 'Peter', 'Cindy'])
r = np.array([5.0, 4.2, 4.3, 5.1, 4.4, 3.7, 3.8, 4.6, 3.2, 3.6, 3.8, 4.7, 4.3, 4.6, 4.2, 3.4])
s = dict(zip(p, r))

n_games = 7

# calculate team combinations
team_combos = list(pulp.combination(p, 2))

# calculate game combinations
# each item is a 3-tuple of tuple(team1), tuple(team2), game_number
legal_games = [(t[0], t[1]) for t in pulp.combination(team_combos, 2) if not set(t[0])&set(t[1])]
game_combos = []
for t, tt in legal_games:
    for game_number in np.arange(n_games) + 1:
        game_combos.append((t, tt, game_number))

# calculate game score differential
game_scores = {}
for gc in game_combos:
    p1, p2 = gc[0]
    p3, p4 = gc[1]
    game_scores[(gc[0], gc[1])] = np.abs((s[p1] + s[p2]) - (s[p3] + s[p4]))

# decision variables
gcvars = pulp.LpVariable.dicts('gc_decvar', game_combos, cat=pulp.LpBinary)

# create problem
# minimize game scores subject to constraints
prob = pulp.LpProblem("PBOpt", pulp.LpMinimize)

# objective function
# minimize difference between team scores
prob += pulp.lpSum([gcvars[gc] * game_scores[(gc[0], gc[1])] for gc in game_combos])

# constraints
# each player must have n_games games
# for player in p:
#     prob += pulp.lpSum([v for k, v in gcvars.items()
#                     if (player in k[0] or player in k[1])]) == n_games

# each player has 1 game per game_number
for player in p:
    for game_number in np.arange(1, n_games + 1):
        prob += pulp.lpSum([v for k, v in gcvars.items()
                            if (player in k[0] or player in k[1]) and
                            k[2] == game_number]) == 1

# do not play with a player more than once
# do not play against a player more than twice
for player, pplayer in team_combos:

    prob += pulp.lpSum([v for k, v in gcvars.items()
                        if (player in k[0] and pplayer in k[0]) or
                        (player in k[1] and pplayer in k[1])]) <= 1
    prob += pulp.lpSum([v for k, v in gcvars.items()
                        if (player in k[0] and pplayer in k[1]) or
                        (player in k[1] and pplayer in k[0])]) <= 2

# solve and print solution
prob.solve()
print([k for k, v in gcvars.items() if v.varValue == 1])

pulp scheduling program needs more efficient problem definition

1 Answers