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:
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])
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...
n_games is redundant because your next constraint forces them to have a game in each roundplayer - 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.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])