我用纸浆写了一个程序来优化我的联赛时间表。 共有16名球员和7个回合。 每轮由4场比赛组成。每场比赛是两人对两人。 每个玩家都有一个等级。 目标是最小化团队之间的绝对评分差异。 约束条件是每个玩家:
下面的代码可以工作,但需要几分钟才能运行。我是一名经验丰富的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])
好消息/坏消息
骨头上还有一点肉可以修剪。有几个循环正在生成冗余元素。坏消息是,解算器通常可以检测到这些,并将它们剔除,因此通过修剪它们,您可能不会获得太大的加速度
三件事
n_games
的限制是多余的,因为你的下一个限制迫使他们在每一轮中都有一场比赛player
-pplayer
约束时,您正在创建许多重复项,因为您隐式地对p
和pp
排序。如果集合P有16个玩家,那么嵌套循环将在忽略P=pp时创建每种类型的P*(P-1)约束。但是,请注意,只有C(16,2)逻辑约束是P*(P-1)/2李>下面是您的程序经过调整的版本。。。。我的机器还在运转,所以我不知道是否能节省时间。您的其他“简单”选项是修补优化差距或超时
我会在这上面再炖一点。。。但我不确定是否有另一种新颖的方法
相关问题 更多 >
编程相关推荐