算法，以最大化具有多个贡献者的唯一集的总和

Question

我正在寻找一种方法来最大化由来自多个来源的贡献组成的公共集合的价值，每个来源的贡献数量固定。

示例问题：3 个人每人有一手牌。每手牌包含一个唯一的集合，但 3 组可以重叠。每个玩家可以选择三张牌来贡献中间。如何最大化 9 张贡献卡的总和，其中

• 每个玩家正好贡献3张牌
• 所有 9 张卡都是唯一的(如果可能)
• 解决方案，可扩展到 200 张可能的"卡"，40 贡献者和各 6 个贡献者。

Answer 1

整数编程听起来像是一种可行的方法。如果不保证，这个问题也感觉很难，这意味着：没有通用算法击败蛮力(没有关于可能输入的假设;IP求解器实际上确实假设了很多/针对现实世界的问题进行了调整)。

(现成的替代办法：约束规划和SAT求解器;CP：易于制定，在组合搜索方面速度更快，但在最大化方面使用分支和绑定样式不太好;SAT：很难表述，因为计数器需要构建，非常快速的组合搜索，再次：没有最大化的概念：需要像转换这样的决策问题)。

这里有一些基于python的完整示例来解决这个问题(在硬约束版本中;每个玩家都必须打出他所有的牌)。由于我使用的是 cvxpy，因此代码非常具有数学风格，尽管不了解 python 或 lib，但应该易于阅读！

在介绍代码之前，一些评论：

一般备注：

• IP 方法在很大程度上依赖于底层求解器！
  • 商业求解器(Gurobi 等)是最好的
  • 优秀的开源求解器：CBC、GLPK、lpsolve
  • cvxpy 中的默认求解器还没有为此做好准备(当增加问题时)！
  • 在我的实验中，使用我的数据，商业求解器扩展得很好！
  • 一个流行的商业求解器需要几秒钟的时间：
    • N_PLAYERS = 40 , CARD_RANGE = (0, 400) , N_CARDS = 200 , N_PLAY = 6
• 使用 cvxpy 不是最佳实践，因为它是为非常不同的用例创建的，这在模型创建时间会导致一些惩罚
  • 我正在使用它，因为我熟悉它并且我喜欢它

改进：问题

• 我们正在解决每个玩家的比赛n_cards在这里
  • 有时没有解决方案
  • 您的模型描述没有正式描述如何处理此问题
  • 改进代码的一般思路：
  • bigM 风格的基于惩罚的目标：例如最大化(n_unique * bigM + classic_score)
    • (其中bigM是一个非常大的数字)

改进：性能

• 我们正在构建所有这些成对冲突，并使用经典的非两者约束
  • 根据任务的不同，冲突的数量可能会增加很多
  • 改进思路(懒得补充)：
    • 计算最大集团的集合并将其添加为约束
    • 会更强大，但是：
      • 对于一般的冲突图，这个问题也应该是NP难的，所以需要使用近似算法
      • (与时间范瓦尔等其他应用程序相反，在这种应用程序中，该集合可以在多项式时间内计算，因为图形将是弦形的)

法典：

import numpy as np
import cvxpy as cvx
np.random.seed(1)
""" Random problem """
N_PLAYERS = 5
CARD_RANGE = (0, 20)
N_CARDS = 10
N_PLAY = 3
card_set = np.arange(*CARD_RANGE)
p = np.empty(shape=(N_PLAYERS, N_CARDS), dtype=int)
for player in range(N_PLAYERS):
p[player] = np.random.choice(card_set, size=N_CARDS, replace=False)
print('Players and their cards')
print(p)
""" Preprocessing:
Conflict-constraints
-> if p[i, j] == p[x, y] => don't allow both
Could be made more efficient
"""
conflicts = []
for p_a in range(N_PLAYERS):
for c_a in range(N_CARDS):
for p_b in range(p_a + 1, N_PLAYERS):  # sym-reduction
if p_b != p_a:
for c_b in range(N_CARDS):
if p[p_a, c_a] == p[p_b, c_b]:
conflicts.append( ((p_a, c_a), (p_b, c_b)) )
# print(conflicts)  # debug
""" Solve """
# Decision-vars
x = cvx.Bool(N_PLAYERS, N_CARDS)
# Constraints
constraints = []
# -> Conflicts
for (p_a, c_a), (p_b, c_b) in conflicts:
# don't allow both -> linearized
constraints.append(x[p_a, c_a] + x[p_b, c_b] <= 1)
# -> N to play
constraints.append(cvx.sum_entries(x, axis=1) == N_PLAY)
# Objective
objective = cvx.sum_entries(cvx.mul_elemwise(p.flatten(order='F'), cvx.vec(x)))  # 2d -> 1d flattening
# ouch -> C vs. Fortran storage
# print(objective)  # debug
# Problem
problem = cvx.Problem(cvx.Maximize(objective), constraints)
problem.solve(verbose=False)
print('MIP solution')
print(problem.status)
print(problem.value)
print(np.round(x.T.value))
sol = x.value
nnz = np.where(abs(sol - 1) <= 0.01)  # being careful with fp-math
sol_p = p[nnz]
assert sol_p.shape[0] == N_PLAYERS * N_PLAY
""" Output solution """
for player in range(N_PLAYERS):
print('player: ', player, 'with cards: ', p[player, :])
print(' plays: ', sol_p[player*N_PLAY:player*N_PLAY+N_PLAY])

输出：

Players and their cards
[[ 3 16  6 10  2 14  4 17  7  1]
[15  8 16  3 19 17  5  6  0 12]
[ 4  2 18 12 11 19  5  6 14  7]
[10 14  5  6 18  1  8  7 19 15]
[15 17  1 16 14 13 18  3 12  9]]
MIP solution
optimal
180.00000005500087
[[ 0.  0.  0.  0.  0.]
[ 0.  1.  0.  1.  0.]
[ 1.  0.  0. -0. -0.]
[ 1. -0.  1.  0.  1.]
[ 0.  1.  1.  1.  0.]
[ 0.  1.  0. -0.  1.]
[ 0. -0.  1.  0.  0.]
[ 0.  0.  0.  0. -0.]
[ 1. -0.  0.  0.  0.]
[ 0.  0.  0.  1.  1.]]
player:  0 with cards:  [ 3 16  6 10  2 14  4 17  7  1]
plays:  [ 6 10  7]
player:  1 with cards:  [15  8 16  3 19 17  5  6  0 12]
plays:  [ 8 19 17]
player:  2 with cards:  [ 4  2 18 12 11 19  5  6 14  7]
plays:  [12 11  5]
player:  3 with cards:  [10 14  5  6 18  1  8  7 19 15]
plays:  [14 18 15]
player:  4 with cards:  [15 17  1 16 14 13 18  3 12  9]
plays:  [16 13  9]

Answer 2

看起来像一个打包问题，您希望打包原始集合的 3 个不相交子集，每个子集的大小为 3，并最大化总和。您可以将其表述为 ILP。在不损失一般性的情况下，我们可以假设这些牌代表从 1 到 N 的自然数。

• 让我们a_i in {0,1}指示玩家是否A打出值为i的牌，其中i在{1,...,N}。请注意，如果玩家A手中没有牌i，则a_i一开始就设置为0。
• 同样，为玩家定义b_i和c_i变量B和C。
• 另外，同样，让我们m_i in {0,1}指示卡i是否会出现在中间，即其中一个玩家将打出价值i的牌。

现在你可以说：

最大化Sum(m_i . i)，但须符合：

对于每个i in {1,...N,}：

1. a_i, b_i, c_i, m_i{0, 1}
2. m_i = a_i + b_i + c_i
3. Sum(a_i) = 3、Sum(b_i) = 3、Sum(c_i) = 3

讨论

请注意，约束 1 和 2 强制每张卡片在中间的唯一性。

我不确定商业或非商业求解器使用此程序可以处理多大的问题，但请注意，这实际上是一个二进制线性程序，可能比一般的 ILP 更容易解决，因此可能值得尝试您正在寻找的大小。

Answer 3

对每只手进行排序，删除重复值。 删除任何手牌中超过第 10 张最高牌(3 手 * 3 张/手，加 1)的任何内容：没有人可以贡献这么低的牌。 出于会计目的，按牌值制作一个目录，显示哪只手持有每个值。 例如，给定玩家 A、B、C 和这些手牌

A [1， 1， 1， 6， 4， 12， 7， 11， 13，

13， 9， 2， 2]

B [13， 2， 3， 1， 5， 5， 8， 9， 11， 10， 5， 5， 9]

C [13， 12， 11， 10， 6， 7， 2， 4，4， 12， 3， 10， 8]

我们会对手进行分类和去重处理。 2 是手牌 C 的第 10 高牌，因此我们删除所有值 2 及以下的值。 然后构建目录

A [13, 12, 11, 9, 7, 6]
B [13, 11, 10, 9, 8, 5, 3]
C [13, 12, 11, 10, 8, 7, 6, 4, 3]
Directory:
13  A B C
12  A C
11  A B C
10  B C
9  A B
8  B C
7  A B
6  A C
5  B
4  C
3  B C

现在，您需要实现一种回溯算法，以某种顺序选择卡片，获取该顺序的总和，并与迄今为止最好的卡片进行比较。 我建议你遍历目录，选择一手牌来获得剩余的最高牌，当你完全用完贡献者时回溯，或者当你得到 9 张牌时。

我建议您维护一些参数以允许您修剪调查，尤其是当您进入较低的值时。

• 设置一个最大可能的值，即目录中前 9 个值的总和。 如果达到此值，请立即停止，因为您已经找到了最佳解决方案。

• 设定一个高起始目标：依次循环浏览手牌，拿走剩余在手牌中可用的最高牌。 在这种情况下，骑自行车 A-B-C，我们将有

  13， 11，12， 9， 10， 8， 7， 5， 6 => 81 注意：因为我选择的值 这恰好提供了一个最佳解决方案。 到目前为止，它将做很多桥手问题空间。

• 计算每手牌贡献了多少张牌;当一个人给了3张牌时，以某种方式取消它的资格：检查选择代码，或将其从目录的本地副本中删除。

当您沿着选择列表向下走时，只要剩余的卡片不足以达到迄今为止最好的总数，请修剪搜索。 例如，如果您在 7 张牌后总共有 71 张牌，并且剩余的最高牌是 5，则停止：您无法使用 5+4 达到 81。

这会让你动起来吗？