基于多个条件，在大型列表中查找所有组合

Question

我正在尝试计算幻想自行车比赛的最佳团队。我有一个包含176名骑手、他们的队伍、他们得分和放入我的团队的价格的csv文件。我试图找到16名骑手中得分最高的团队。

适用于任何团队组成的规则是：

• 团队的总成本不能超过100。
• 同一支队伍中的骑手不得超过4人。

下面是我的csv文件的简短摘录。

THOMAS Geraint,Team INEOS,142,13
SAGAN Peter,BORA - hansgrohe,522,11.5
GROENEWEGEN Dylan,Team Jumbo-Visma,205,11
FUGLSANG Jakob,Astana Pro Team,46,10
BERNAL Egan,Team INEOS,110,10
BARDET Romain,AG2R La Mondiale,21,9.5
QUINTANA Nairo,Movistar Team,58,9.5
YATES Adam,Mitchelton-Scott,40,9.5
VIVIANI Elia,Deceuninck - Quick Step,273,9.5
YATES Simon,Mitchelton-Scott,13,9
EWAN Caleb,Lotto Soudal,13,9

解决这个问题最简单的方法是生成所有可能的团队组合列表，然后应用规则来排除不符合前述规则的团队。之后，很容易计算每个团队的总分，并选择得分最高的团队。理论上，可以通过以下代码生成可用团队列表。

database_csv = pd.read_csv('renner_db_example.csv')
renners = database_csv.to_dict(orient='records')

budget = 100
max_same_team = 4
team_total = 16

combos = itertools.combinations(renners,team_total)
usable_combos = []

for i in combos:
    if sum(persoon["Waarde"] for persoon in i)  < budget and all(z <= max_same_team for z in [len(list(group)) for key, group in groupby([persoon["Ploeg"] for persoon in i])]) == True:   
    usable_combos.append(i)    

然而，将一个由176名骑行者组成的列表计算出16人团队的所有组合，对于我的电脑来说只是太多计算量，即使这个问题的答案似乎暗示了其他情况。我已经进行了一些研究，但没有找到任何不必迭代每个选项就可以应用上述条件的方法。

有没有办法通过使上述方法生效或使用其他方法找到最佳团队？ 编辑： 在文本中，完整的CSV文件可以在这里找到。

- Thakkennes

---

这可能是一个根本性难题。看起来类似于背包问题：https://en.wikipedia.org/wiki/Knapsack_problem - Kyle Parsons

我已经添加了完整CSV文件的链接。 - Thakkennes

我认为要先生成所有的组合，然后再剪枝无效的团队。你需要首先生成20062118235172477959495个组合（其中n为176，k为16）。这个值代表从176个元素中选择16个元素的可能组合数。 - Paul M.

看起来像是一个离散优化问题。也许你可以在这里或者这里找到一些灵感：http://www.pyopt.org/reference/introduction.html 或者 https://www.coursera.org/learn/discrete-optimization。 - Dan

通过保持总成本<100来最大化总点数的目的是什么？ - Ajay Srivastava

Answer 1

这是一个经典的运筹学问题。

有很多算法可以找到最优解（或者根据算法找到一个非常好的解）：

• 混合整数规划
• 元启发式算法
• 约束编程
• ...

以下是使用MIP、ortools库和默认求解器COIN-OR找到最优解的代码：

from ortools.linear_solver import pywraplp
import pandas as pd


solver = pywraplp.Solver('cyclist', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)    
cyclist_df = pd.read_csv('cyclists.csv')

# Variables

variables_name = {}
variables_team = {}

for _, row in cyclist_df.iterrows():
    variables_name[row['Naam']] = solver.IntVar(0, 1, 'x_{}'.format(row['Naam']))
    if row['Ploeg'] not in variables_team:
        variables_team[row['Ploeg']] = solver.IntVar(0, solver.infinity(), 'y_{}'.format(row['Ploeg']))

# Constraints

# Link cyclist <-> team
for team, var in variables_team.items():
    constraint = solver.Constraint(0, solver.infinity())
    constraint.SetCoefficient(var, 1)
    for cyclist in cyclist_df[cyclist_df.Ploeg == team]['Naam']:
        constraint.SetCoefficient(variables_name[cyclist], -1)

# Max 4 cyclist per team
for team, var in variables_team.items():
    constraint = solver.Constraint(0, 4)
    constraint.SetCoefficient(var, 1)

# Max cyclists
constraint_max_cyclists = solver.Constraint(16, 16)
for cyclist in variables_name.values():
    constraint_max_cyclists.SetCoefficient(cyclist, 1)

# Max cost
constraint_max_cost = solver.Constraint(0, 100)
for _, row in cyclist_df.iterrows():
    constraint_max_cost.SetCoefficient(variables_name[row['Naam']], row['Waarde'])    

# Objective 
objective = solver.Objective()
objective.SetMaximization()

for _, row in cyclist_df.iterrows():
    objective.SetCoefficient(variables_name[row['Naam']], row['Punten totaal:'])

# Solve and retrieve solution     
solver.Solve()

chosen_cyclists = [key for key, variable in variables_name.items() if variable.solution_value() > 0.5]

print(cyclist_df[cyclist_df.Naam.isin(chosen_cyclists)])

打印：

    Naam                Ploeg                       Punten totaal:  Waarde
1   SAGAN Peter         BORA - hansgrohe            522             11.5
2   GROENEWEGEN         Dylan   Team Jumbo-Visma    205             11.0
8   VIVIANI Elia        Deceuninck - Quick Step     273             9.5
11  ALAPHILIPPE Julian  Deceuninck - Quick Step     399             9.0
14  PINOT Thibaut       Groupama - FDJ              155             8.5
15  MATTHEWS Michael    Team Sunweb                 323             8.5
22  TRENTIN Matteo      Mitchelton-Scott            218             7.5
24  COLBRELLI Sonny     Bahrain Merida              238             6.5
25  VAN AVERMAET Greg   CCC Team                    192             6.5
44  STUYVEN Jasper      Trek - Segafredo            201             4.5
51  CICCONE Giulio      Trek - Segafredo            153             4.0
82  TEUNISSEN Mike      Team Jumbo-Visma            255             3.0
83  HERRADA Jesús       Cofidis, Solutions Crédits  255             3.0
104 NIZZOLO Giacomo     Dimension Data              121             2.5
123 MEURISSE Xandro     Wanty - Groupe Gobert       141             2.0
151 TRATNIK Jan Bahrain Merida                      87              1.0

---

这段代码是如何解决问题的？正如@KyleParsons所说，它看起来像背包问题，并可以使用整数规划进行建模。

让我们定义变量Xi（0 <= i <= nb_cyclists）和Yj（0 <= j <= nb_teams）。

Xi = 1 if cyclist n°i is chosen, =0 otherwise

Yj = n where n is the number of cyclists chosen within team j

为了定义这些变量之间的关系，可以建立以下约束模型：

# Link cyclist <-> team
For all j, Yj >= sum(Xi, for all i where Xi is part of team j)

为了每个团队最多只选出4名自行车手，您需要设置以下约束条件：

# Max 4 cyclist per team
For all j, Yj <= 4

为了选择16名自行车手，这里有相关的限制条件：

# Min 16 cyclists 
sum(Xi, 1<=i<=nb_cyclists) >= 16
# Max 16 cyclists 
sum(Xi, 1<=i<=nb_cyclists) <= 16

成本约束：

# Max cost 
sum(ci * Xi, 1<=i<=n_cyclists) <= 100 
# where ci = cost of cyclist i

然后你可以最大化{{某个功能或效益}}。

# Objective
max sum(pi * Xi, 1<=i<=n_cyclists)
# where pi = nb_points of cyclist i

请注意，我们使用线性目标和线性不等式约束来建模问题。如果Xi和Yj是连续变量，则该问题将是多项式（线性规划），可以使用以下方法解决：

• 内点法（多项式解决方案）
• 单纯形法（非多项式但在实践中更有效）

由于这些变量是整数（整数规划或混合整数规划），因此该问题被认为是NP完全类的一部分（除非您是天才，否则无法使用多项式解决方案解决）。像COIN-OR这样的求解器使用复杂的分支和界限或分支和割方法来高效地解决它们。 ortools提供了一个很好的包装器，可用于在Python中使用COIN。这些工具是免费且开源的。

所有这些方法都具有找到最优解的优点，而无需迭代所有可能的解决方案（并显着减少组合数）。

- Corentin Limier

---

非常有趣，非常感谢您详尽的回答！ - Thakkennes

我认为你添加的解释非常清晰。然而，我发现这里提供的文档有点简略。 我的最终目标是找到最佳的16人团队，在每个阶段选择最好的10名骑手。我发布的CSV实际上已经被修改过了，我的原始CSV还包含每个骑手在每个阶段得分的列表。这个列表看起来像这样[0, 40, 13, 0, 2, 55, 1, 17, 0, 14]。我能否通过简单修改目标来实现这一点，还是必须大幅修改代码？ - Thakkennes

这正是这个问题的难点所在。我正在尝试找到表现最佳的团队。因此，我有一个由16名自行车手组成的池子，其中10名自行车手的得分计入每天的得分。然后将每天的得分相加以获得总分。目的是尽可能提高这个最终总分。我目前认为可以通过为每个阶段设置一个目标系数来实现这一目标，但无法确定如何实现每个阶段只计算十名最佳骑手的得分对最终得分的影响。 - Thakkennes

@Thakkennes，我为新问题发布了一个新答案。 - Corentin Limier

Answer 2

我为你的问题添加了另一个答案：

引用： 我发布的CSV实际上是修改过的，我的原始CSV还包含每个骑手的列表，其中包含他们在每个阶段的得分。此列表看起来像这样[0, 40, 13, 0, 2, 55, 1, 17, 0, 14]。我正在尝试找到表现最好的团队。因此，我有一个由16名自行车手组成的团队，其中10名自行车手的得分计入每天的得分。然后将每天的得分相加以获得总得分。目的是尽可能提高这个最终总得分。

如果您认为我应该编辑我的第一篇帖子，请告诉我，因为我认为这样更清晰，因为我的第一篇帖子相当密集并回答了最初的问题。

让我们介绍一个新变量：

Zik = 1 if cyclist i is selected and is one of the top 10 in your team on day k

您需要将这些约束条件添加到链接变量Zik和Xi（如果自行车手i未被选中，即如果Xi = 0，则变量Zik不能等于1）中。

For all i, sum(Zik, 1<=k<=n_days) <= n_days * Xi

每天只能选出10名骑自行车的人，这是一种限制条件。

For all k, sum(Zik, 1<=i<=n_cyclists) <= 10

最后，您的目标可以写成这样：

Maximize sum(pik * Xi * Zik, 1<=i<=n_cyclists, 1 <= k <= n_days)
# where pik = nb_points of cyclist i at day k

这里是思考的部分。像这样写的目标并不是线性的（注意两个变量X和Z之间的乘法）。幸运的是，这里有二进制，并且有一个技巧可以将这个公式转换为其线性形式。

让我们引入新的变量Lik（Lik = Xi * Zik），以线性化目标函数。

现在，目标函数可以写成以下形式，并且是线性的：

Maximize sum(pik * Lik, 1<=i<=n_cyclists, 1 <= k <= n_days)
# where pik = nb_points of cyclist i at day k

现在我们需要添加这些约束条件，使得Lik等于Xi * Zik：

For all i,k : Xi + Zik - 1 <= Lik
For all i,k : Lik <= 1/2 * (Xi + Zik)

“Voilà”是法语，意思是“瞧！”、“看这个！”。所以这句话的意思是：“瞧！这就是数学之美，你可以用线性方程来模拟很多东西。我介绍了一些高级概念，如果你一开始不理解也很正常。”

---

我在这个文件中模拟了每天的得分列。

以下是解决新问题的Python代码：

import ast
from ortools.linear_solver import pywraplp
import pandas as pd


solver = pywraplp.Solver('cyclist', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
cyclist_df = pd.read_csv('cyclists_day.csv')
cyclist_df['Punten_day'] = cyclist_df['Punten_day'].apply(ast.literal_eval)

# Variables
variables_name = {}
variables_team = {}
variables_name_per_day = {}
variables_linear = {}

for _, row in cyclist_df.iterrows():
    variables_name[row['Naam']] = solver.IntVar(0, 1, 'x_{}'.format(row['Naam']))
    if row['Ploeg'] not in variables_team:
        variables_team[row['Ploeg']] = solver.IntVar(0, solver.infinity(), 'y_{}'.format(row['Ploeg']))

    for k in range(10):
        variables_name_per_day[(row['Naam'], k)] = solver.IntVar(0, 1, 'z_{}_{}'.format(row['Naam'], k))
        variables_linear[(row['Naam'], k)] = solver.IntVar(0, 1, 'l_{}_{}'.format(row['Naam'], k))

# Link cyclist <-> team
for team, var in variables_team.items():
    constraint = solver.Constraint(0, solver.infinity())
    constraint.SetCoefficient(var, 1)
    for cyclist in cyclist_df[cyclist_df.Ploeg == team]['Naam']:
        constraint.SetCoefficient(variables_name[cyclist], -1)

# Max 4 cyclist per team
for team, var in variables_team.items():
    constraint = solver.Constraint(0, 4)
    constraint.SetCoefficient(var, 1)

# Max cyclists
constraint_max_cyclists = solver.Constraint(16, 16)
for cyclist in variables_name.values():
    constraint_max_cyclists.SetCoefficient(cyclist, 1)

# Max cost
constraint_max_cost = solver.Constraint(0, 100)
for _, row in cyclist_df.iterrows():
    constraint_max_cost.SetCoefficient(variables_name[row['Naam']], row['Waarde'])

# Link Zik and Xi
for name, cyclist in variables_name.items():
    constraint_link_cyclist_day = solver.Constraint(-solver.infinity(), 0)
    constraint_link_cyclist_day.SetCoefficient(cyclist, - 10)
    for k in range(10):
        constraint_link_cyclist_day.SetCoefficient(variables_name_per_day[name, k], 1)

# Min/Max 10 cyclists per day
for k in range(10):
    constraint_cyclist_per_day = solver.Constraint(10, 10)
    for name in cyclist_df.Naam:
        constraint_cyclist_per_day.SetCoefficient(variables_name_per_day[name, k], 1)

# Linearization constraints 
for name, cyclist in variables_name.items():
    for k in range(10):
        constraint_linearization1 = solver.Constraint(-solver.infinity(), 1)
        constraint_linearization2 = solver.Constraint(-solver.infinity(), 0)

        constraint_linearization1.SetCoefficient(cyclist, 1)
        constraint_linearization1.SetCoefficient(variables_name_per_day[name, k], 1)
        constraint_linearization1.SetCoefficient(variables_linear[name, k], -1)

        constraint_linearization2.SetCoefficient(cyclist, -1/2)
        constraint_linearization2.SetCoefficient(variables_name_per_day[name, k], -1/2)
        constraint_linearization2.SetCoefficient(variables_linear[name, k], 1)

# Objective 
objective = solver.Objective()
objective.SetMaximization()

for _, row in cyclist_df.iterrows():
    for k in range(10):
        objective.SetCoefficient(variables_linear[row['Naam'], k], row['Punten_day'][k])

solver.Solve()

chosen_cyclists = [key for key, variable in variables_name.items() if variable.solution_value() > 0.5]

print('\n'.join(chosen_cyclists))

for k in range(10):
    print('\nDay {} :'.format(k + 1))
    chosen_cyclists_day = [name for (name, day), variable in variables_name_per_day.items() 
                       if (day == k and variable.solution_value() > 0.5)]
    assert len(chosen_cyclists_day) == 10
    assert all(chosen_cyclists_day[i] in chosen_cyclists for i in range(10))
    print('\n'.join(chosen_cyclists_day))

这是结果：

你的团队：

SAGAN Peter
GROENEWEGEN Dylan
VIVIANI Elia
ALAPHILIPPE Julian
PINOT Thibaut
MATTHEWS Michael
TRENTIN Matteo
COLBRELLI Sonny
VAN AVERMAET Greg
STUYVEN Jasper
BENOOT Tiesj
CICCONE Giulio
TEUNISSEN Mike
HERRADA Jesús
MEURISSE Xandro
GRELLIER Fabien

每天选择的自行车骑手

Day 1 :
SAGAN Peter
VIVIANI Elia
ALAPHILIPPE Julian
MATTHEWS Michael
COLBRELLI Sonny
VAN AVERMAET Greg
STUYVEN Jasper
CICCONE Giulio
TEUNISSEN Mike
HERRADA Jesús

Day 2 :
SAGAN Peter
ALAPHILIPPE Julian
MATTHEWS Michael
TRENTIN Matteo
COLBRELLI Sonny
VAN AVERMAET Greg
STUYVEN Jasper
TEUNISSEN Mike
NIZZOLO Giacomo
MEURISSE Xandro

Day 3 :
SAGAN Peter
GROENEWEGEN Dylan
VIVIANI Elia
MATTHEWS Michael
TRENTIN Matteo
VAN AVERMAET Greg
STUYVEN Jasper
CICCONE Giulio
TEUNISSEN Mike
HERRADA Jesús

Day 4 :
SAGAN Peter
VIVIANI Elia
PINOT Thibaut
MATTHEWS Michael
TRENTIN Matteo
COLBRELLI Sonny
VAN AVERMAET Greg
STUYVEN Jasper
TEUNISSEN Mike
HERRADA Jesús

Day 5 :
SAGAN Peter
VIVIANI Elia
ALAPHILIPPE Julian
PINOT Thibaut
MATTHEWS Michael
TRENTIN Matteo
COLBRELLI Sonny
VAN AVERMAET Greg
CICCONE Giulio
HERRADA Jesús

Day 6 :
SAGAN Peter
GROENEWEGEN Dylan
VIVIANI Elia
ALAPHILIPPE Julian
MATTHEWS Michael
TRENTIN Matteo
COLBRELLI Sonny
STUYVEN Jasper
CICCONE Giulio
TEUNISSEN Mike

Day 7 :
SAGAN Peter
VIVIANI Elia
ALAPHILIPPE Julian
MATTHEWS Michael
COLBRELLI Sonny
VAN AVERMAET Greg
STUYVEN Jasper
TEUNISSEN Mike
HERRADA Jesús
MEURISSE Xandro

Day 8 :
SAGAN Peter
GROENEWEGEN Dylan
VIVIANI Elia
ALAPHILIPPE Julian
MATTHEWS Michael
STUYVEN Jasper
TEUNISSEN Mike
HERRADA Jesús
NIZZOLO Giacomo
MEURISSE Xandro

Day 9 :
SAGAN Peter
GROENEWEGEN Dylan
VIVIANI Elia
ALAPHILIPPE Julian
PINOT Thibaut
TRENTIN Matteo
COLBRELLI Sonny
VAN AVERMAET Greg
TEUNISSEN Mike
HERRADA Jesús

Day 10 :
SAGAN Peter
GROENEWEGEN Dylan
VIVIANI Elia
PINOT Thibaut
COLBRELLI Sonny
STUYVEN Jasper
CICCONE Giulio
TEUNISSEN Mike
HERRADA Jesús
NIZZOLO Giacomo

---

让我们比较答案1和答案2的结果print(solver.Objective().Value()):

第一个模型得到3738.0，第二个模型得到3129.087388325567。第二个模型得到的值更低，因为您只选择了每个阶段的10名自行车手，而不是16名。

现在，如果保留第一个解决方案并使用新的评分方法，我们得到3122.9477585307413 我们可以认为第一个模型已经足够好了：我们不需要引入新的变量/约束条件，模型保持简单，并且我们得到的解决方案几乎与复杂模型一样好。有时候不必完全精确，通过一些近似方法可以更轻松快速地解决模型。

- Corentin Limier

---

非常感谢！这看起来很不错。但是，当我尝试使用正确每日分数的 CSV 运行它时，在第4天我会得到一个 AssertionError，只选择了9名骑手。我无法确定是什么原因，因为我还没有完全深入研究您的代码。你有任何想法是什么造成了这个问题吗？我已经贴出了我正在使用的 CSV 这里。 - Thakkennes

我已经找到了问题所在。每天骑车人数的限制被设置为最多10名骑手，但这也使得它可能少于10人。因此，这个限制应该是constraint_cyclist_per_day = solver.Constraint(10, 10)，这样它就没有其他选择，只能选择10名骑手。仅为了清晰起见，这应该是您代码中的第56行。 - Thakkennes

@Thakkennes 没错！第5天只有6名自行车手的得分>0。实际模型选择超过6个是没有必要的。你的修复很完美，很高兴你找到了它。 - Corentin Limier