最大化具有多个贡献者的唯一集总和的算法
algorithm to maximize sum of unique set with multiple contributors
我正在寻找一种方法来最大化公共集合的价值，该集合由多个来源的贡献组成，每个来源的贡献数量固定。
例题：3个人各有一手牌。每只手都包含一个独特的集合，但 3 个集合可能会重叠。每个玩家可以挑选三张牌贡献给中间。如何最大化 9 张贡献卡片的总和
- 每个玩家刚好贡献 3 张牌
- 所有 9 张牌都是独一无二的（如果可能的话）
- 可以在 200 范围内缩放的解决方案 "cards", 40
每个贡献者和 6 个贡献。
对每只手进行排序，删除重复值。删除超过任何手牌中第 10 大牌的任何东西（3 手牌 * 3 cards/hand，加 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
// 注意：因为我选择的值
// 这恰好提供了最佳解决方案。
// 到目前为止，它会解决很多桥手问题 space。
统计每手贡献了多少张牌；当一个人给出了它的 3 张卡片时，以某种方式取消它的资格：检查选择代码，或者从目录的本地副本中删除它。
当您沿着选择列表走下去时，只要剩余的卡片不足以达到迄今为止最好的总数，就进行搜索。比如7张牌后你的总点数是71，剩下的最高牌是5，停止：你5+4是到不了81的。
这让你感动吗？
看起来像 packing problem, where you want to pack 3 disjoint subsets of your original sets, each of size 3, and maximize the sum. You can formulate it as an ILP。不失一般性，我们可以假设卡片代表从 1 到 N 的自然数。
- 让
a_i in {0,1} 表示玩家 A 是否打出价值 i 的牌，其中 i 在 {1,...,N} 中。请注意，如果玩家 A 手上没有牌 i，则 a_i 一开始会设置为 0。
- 同样，为玩家
B和C定义b_i和c_i变量。
- 同样，让
m_i in {0,1}表示卡i是否会出现在中间，即其中一位玩家将打出一张价值i的卡。
现在你可以说：
最大化 Sum(m_i . i)，受制于：
每个 i in {1,...N,}:
a_i, b_i, c_i, m_i 在 {0, 1}m_i = a_i + b_i + c_iSum(a_i) = 3、Sum(b_i) = 3、Sum(c_i) = 3
讨论
注意约束 1 和 2，强制中间每张卡片的唯一性。
我不确定商业或非商业求解器可以用这个程序处理多大的问题，但请注意，这实际上是一个二进制线性程序，它可能比一般的 ILP 更容易解决, 因此可能值得尝试您正在寻找的尺码。
整数规划听起来是一种可行的方法。在没有保证的情况下，这个问题也感觉 NP-hard，这意味着：没有通用的算法可以击败蛮力（没有对可能输入的假设；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 不是最佳实践，因为它是为非常不同的用例创建的，这会在模型创建时间上引起一些损失
- 我使用它是因为我熟悉它并且我喜欢它
改进：问题
- 我们正在解决这里的each-player-plays-exactly-n_cards
- 有时无解
- 您的模型描述没有正式描述如何处理这个
- 改进代码的总体思路：
- bigM-style penalty-based objective：例如最大化（n_unique * bigM + classic_score）
- （其中 bigM 是一个很大的数字）
改进：性能
- 我们正在构建所有这些成对冲突并使用经典的 not-both 约束
- 冲突的数量，根据任务可以增长很多
- 改进思路（懒得补充）：
- 计算最大派系集并将其添加为约束
- 会更强大，但是：
- 对于一般的冲突图，这个问题也应该是 NP-hard，所以需要使用近似算法
- （与时间间隔等其他应用程序相反，在这些应用程序中，该集合可以在多项式时间内计算，因为图形将是弦图）
代码：
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]
我正在寻找一种方法来最大化公共集合的价值，该集合由多个来源的贡献组成，每个来源的贡献数量固定。
例题：3个人各有一手牌。每只手都包含一个独特的集合，但 3 个集合可能会重叠。每个玩家可以挑选三张牌贡献给中间。如何最大化 9 张贡献卡片的总和
- 每个玩家刚好贡献 3 张牌
- 所有 9 张牌都是独一无二的（如果可能的话）
- 可以在 200 范围内缩放的解决方案 "cards", 40 每个贡献者和 6 个贡献。
对每只手进行排序，删除重复值。删除超过任何手牌中第 10 大牌的任何东西（3 手牌 * 3 cards/hand，加 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 // 注意：因为我选择的值 // 这恰好提供了最佳解决方案。 // 到目前为止，它会解决很多桥手问题 space。
统计每手贡献了多少张牌；当一个人给出了它的 3 张卡片时，以某种方式取消它的资格：检查选择代码，或者从目录的本地副本中删除它。
当您沿着选择列表走下去时，只要剩余的卡片不足以达到迄今为止最好的总数，就进行搜索。比如7张牌后你的总点数是71，剩下的最高牌是5，停止：你5+4是到不了81的。
这让你感动吗？
看起来像 packing problem, where you want to pack 3 disjoint subsets of your original sets, each of size 3, and maximize the sum. You can formulate it as an ILP。不失一般性，我们可以假设卡片代表从 1 到 N 的自然数。
- 让
a_i in {0,1}表示玩家A是否打出价值i的牌，其中i在{1,...,N}中。请注意，如果玩家A手上没有牌i，则a_i一开始会设置为0。 - 同样，为玩家
B和C定义b_i和c_i变量。 - 同样，让
m_i in {0,1}表示卡i是否会出现在中间，即其中一位玩家将打出一张价值i的卡。
现在你可以说：
最大化 Sum(m_i . i)，受制于：
每个 i in {1,...N,}:
a_i, b_i, c_i, m_i在{0, 1}m_i = a_i + b_i + c_iSum(a_i) = 3、Sum(b_i) = 3、Sum(c_i) = 3
讨论
注意约束 1 和 2，强制中间每张卡片的唯一性。
我不确定商业或非商业求解器可以用这个程序处理多大的问题，但请注意，这实际上是一个二进制线性程序，它可能比一般的 ILP 更容易解决, 因此可能值得尝试您正在寻找的尺码。
整数规划听起来是一种可行的方法。在没有保证的情况下，这个问题也感觉 NP-hard，这意味着：没有通用的算法可以击败蛮力（没有对可能输入的假设；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 不是最佳实践，因为它是为非常不同的用例创建的，这会在模型创建时间上引起一些损失
- 我使用它是因为我熟悉它并且我喜欢它
改进：问题
- 我们正在解决这里的each-player-plays-exactly-n_cards
- 有时无解
- 您的模型描述没有正式描述如何处理这个
- 改进代码的总体思路：
- bigM-style penalty-based objective：例如最大化（n_unique * bigM + classic_score）
- （其中 bigM 是一个很大的数字）
改进：性能
- 我们正在构建所有这些成对冲突并使用经典的 not-both 约束
- 冲突的数量，根据任务可以增长很多
- 改进思路（懒得补充）：
- 计算最大派系集并将其添加为约束
- 会更强大，但是：
- 对于一般的冲突图，这个问题也应该是 NP-hard，所以需要使用近似算法
- （与时间间隔等其他应用程序相反，在这些应用程序中，该集合可以在多项式时间内计算，因为图形将是弦图）
代码：
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]