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

Question

我用 PuLP 编写了一个程序来优化我的联赛赛程。有16名球员和7轮比赛。每轮由 4 场比赛组成。每场比赛都是两名球员对两名球员。每个玩家都有一个等级。 objective 是为了最小化团队之间的绝对评分差异。限制是每个玩家：

必须打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

好消息news/Bad...

那里的骨头上还有一点肉，你可以 trim。您有几个生成冗余元素的循环。坏消息是解算器通常可以检测到这些并将它们清除掉，所以你可能不会通过 trimming 它们获得太多加速。

3 件事...

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

以下是您的程序的调整版本....它仍在我的机器上运行，所以我不知道是否可以节省任何时间。您的其他“简单”选项是修补最优性差距或超时。

我会在这方面多加考虑......但我不确定是否有另一种新颖的方法。

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

python

linear-programming

pulp