纸浆调度程序需要更有效的问题定义

Question

我用PuLP编写了一个程序来优化我的联赛时间表。共有16名选手和7轮比赛。每轮比赛由4场比赛组成。每场比赛是两名选手对两名选手。每个玩家都有一个等级。目标是最大限度地减少团队之间的绝对评分差异。限制是每个玩家：

• 必须打7轮
• 每轮只能玩1场游戏
• 只能与其他玩家搭档0或1次
• 只能是其他玩家0、1或2次的对手

下面的代码可以工作，但运行需要几分钟时间。我是一名经验丰富的python程序员，但在线性编程方面相对来说还是个新手，所以我不确定是否可以更有效地定义问题以加快解决时间。

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

Answer 1

好消息/坏消息。。。

骨头上还剩下一点肉，你可以修剪一下。您有几个循环正在生成冗余元素。坏消息是，解算器通常可以检测到这些并将其剔除，因此通过修剪它们可能不会获得太多加速度。

3件事。。。

1. 你对玩家必须拥有n_games的约束是多余的，因为你的下一个约束迫使他们在每一轮中都有一场比赛
2. 当您创建player-pplayer约束时，您会创建许多重复项，因为您隐式地对p和pp进行排序。如果集合P有16个参与者，那么当忽略P=pp时，嵌套循环将创建每种类型的P*(P-1(约束。然而，请注意，只有C(16,2(逻辑约束，它是p*(p-1(/2
3. 在创建一套法律游戏时，你也在做类似的事情，因为你在暗中命令法律团队

以下是您的程序的调整版本。。。。它还在我的机器上翻腾，所以我不知道是否能节省时间。你的另一个"；"容易"；选项是修补一个最优性缺口或一个超时。

我再炖一点。。。但我不确定是否还有其他新颖的方法。

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