选择足球队球员的组合优化

Question

我正在考虑使用整数规划来生成组成球队的最佳足球运动员组合。

虽然问题本身很简单，但我无法为职位资格制定有效的约束条件。

我在 Whosebug 上搜索了经典整数规划问题的变体，并提出了一个临时解决方案，但想验证当前的解决方案是否有效。

问题
Select 从一组有限的潜在球员中选出 11 名足球队球员。
球队由 11 个位置组成：5 名进攻队员、5 名防守队员和 1 名守门员。
每个角色都有各自的合格玩家池。
（例如守门员只能从一组有手套的球员中选出）
每个玩家都分配了一个 'skill score' 代表他们的技能

Objective函数
最大化：所有 11 位玩家技能得分的总和

约束条件

1. 所有 11 个位置必须至少有 1 名玩家填满
2. 1 名玩家只能占用 1 个位置
3. 每个位置必须由有资格担任该角色的球员填补

我的临时解决方案

Let xij: player i in consideration for slot j (j=1, 2,..., 11, 1 <= i <= n)
and w: n x 1 weight matrix representing skill score for player i

1. sum_j(xij) == 1 for each slot j
2. 0 <= sum_i(xij) <= 1 for each player i
3. 0 <= xij <= 1 if player i is eligible for slot j, == 0 otherwise

maximize sum(wTx)

我还想不出一个优雅的方法来操作 3，所以我现在的答案是将每个单元格硬编码为 0。

我打算在 Python（cvxpy 或 PuLP）中使用整数编程库。

当前的设计会导致收敛或计算时间方面的任何问题吗？

是否有更有效的方法来模拟问题？

备注

• 为简单起见，我们假设一个玩家可以担任多个角色，但他们的技能点不会因角色而改变
• 如果玩家的技能分数根据他们与其他玩家的协同作用发生变化，问题的表述是否会发生变化？我在想，简单地通过 nC2 可能的相互作用扩展 x 矩阵就可以了，但我很好奇是否有更好的解决方案。

Answer 1

您的 IP 公式看起来不错。不过这个问题也可以用动态规划来解决：

让数组 dp[n][mask] 表示将玩家从 1 到 n 放置到 mask 的二进制表示中的 0 数字对应的位置时可以获得的最大可能分数。例如 dp[5][0b11111110101] 等于将玩家 1 到 5 放置到位置 2 和 4 可以获得的最大分数。（掩码的第二和第四位为零。）

现在我们递归定义dp[n][mask]:

dp[n][mask] = max{
    dp[n-1][mask], # the case when we don't use player n
    max_j{ dp[n-1][mask|(1<<j)] + w[n] } (1 <= j <= 11 and mask's jth bit is 0)
}

基本情况是 n=0。

dp[0][mask] = {
    -infinity, if there are 0 bits in mask # there are empty positions left, we want to strictly discourage this case.
    0, if all 11 bits of mask is 1
}