我正在寻找一种方法来最大化由多个来源组成的共同集合的价值，每个来源都有固定数量的贡献。
示例问题：3个人各自拥有一手牌。每手牌包含一个唯一的集合，但3个集合可能重叠。每个玩家可以选择三张牌作为贡献放在中间。如何最大化9张贡献牌的总和，其中：
- 每个玩家恰好贡献3张牌
- 所有9张牌都是唯一的（如果可能）
- 解决方案能够扩展到200个可能的“牌”，40个贡献者和每个贡献者6个贡献。
用于最大化多个贡献者的唯一集合总和的算法。
3
- Chris.Caldwell
1
请使用您在回答中提供的细节更新问题描述。我不希望其他人因为原始示例看起来不太有趣而对问题置之不理。 - Prune
3个回答
1
Integer programming听起来是一个可行的方法。虽然不能保证，但这个问题感觉也是NP难的，意味着：没有通用算法能够击败暴力搜索（没有对可能输入做出任何假设；解整数规划实际上做了很多假设/针对真实世界问题进行了调整）。
（替代现成方法：约束规划和SAT求解器；CP：易于表述，在组合搜索方面更快，但在最大化方面使用分支定界样式不如好；SAT：作为计数器需要构建，很快的组合搜索，再次强调：没有最大化概念：需要类似于决策问题的转换。）
以下是解决该问题的基于Python的完整示例（在硬约束版本中；每个玩家都必须打出他的所有牌）。由于我使用了cvxpy，所以代码相当数学化，即使不知道Python或库，也应该很容易阅读！
在呈现代码之前，有一些注释：
一般备注：
（替代现成方法：约束规划和SAT求解器；CP：易于表述，在组合搜索方面更快，但在最大化方面使用分支定界样式不如好；SAT：作为计数器需要构建，很快的组合搜索，再次强调：没有最大化概念：需要类似于决策问题的转换。）
以下是解决该问题的基于Python的完整示例（在硬约束版本中；每个玩家都必须打出他的所有牌）。由于我使用了cvxpy，所以代码相当数学化，即使不知道Python或库，也应该很容易阅读！
在呈现代码之前，有一些注释：
一般备注：
- IP方法严重依赖于底层求解器！
- 商业求解器（如Gurobi等）是最好的选择
- 开源求解器：CBC、GLPK和lpsolve
- cvxpy中的默认求解器在增加问题规模时不太适用！
- 在我的实验中，使用商业求解器的可扩展性非常好！
- 一种流行的商业求解器需要几秒钟来解决以下问题：
N_PLAYERS = 40, CARD_RANGE = (0, 400), N_CARDS = 200, N_PLAY = 6
- 使用cvxpy并不是最佳实践，因为它是为非常不同的用例创建的，这会在模型创建时间上产生一些惩罚。
- 我使用它是因为我熟悉它并喜欢它
改进：问题
- 我们正在解决每个玩家都只能出n张牌的问题
- 有时候没有解决方案
- 您的模型描述没有正式说明如何处理这个问题
- 改进代码的一般思路：
- 基于bigM惩罚的目标函数：例如Maximize（n_unique * bigM + classic_score）
- （其中bigM是一个非常大的数字）
改进：性能
- 我们正在构建所有这些成对冲突，并使用经典的not-both约束
- 冲突数量，取决于任务可能会增加很多
- 改进思路（太懒了，不想添加）：
- 计算最大团集合并将其添加为约束
- 将更加强大，但：
- 对于一般的冲突图，这个问题也应该是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]
- sascha
1
看起来像是一个装箱问题，你想要将原始集合划分为3个大小为3的不相交子集，并最大化它们的和。你可以将其表示为一个整数线性规划问题。不失一般性地，我们可以假设卡片代表从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强制每张卡片在中间的唯一性。
我不确定商业或非商业求解器可以处理多大的问题，但请注意，这实际上是一个二进制线性规划问题，比一般的整数线性规划问题更容易解决，因此对于您寻找的规模可能值得尝试。
- Ari
6
这是一个很好的方法，谢谢。我认为这已经非常接近了，除了a_i、b_i、c_i是身份证明，如果Sum(a_i.x_i)=3，则[a,b,c]_i必须全部等于1。然而，m_i是卡牌的价值，因为我们要最大化总分数。这就是我现在所拥有的所有见解，我需要再多阅读一些解决方案和实现，并回来看看，但这绝对是一个非常好的方法。 - Chris.Caldwell
@Chris.Caldwell：我修正了我的答案，现在我认为它是正确的。 - Ari
请注意，这确实是一个二元线性规划问题，比一般的整数线性规划问题更简单，但这是一个危险的简化，在实践中并不一定正确（使用那些通用求解器）。我没有尝试过您的方法，但是，对于他的示例维度，使用商业求解器与我的整数规划和随机数据（仅限二进制；但在这些算法中并不重要）进行了求解。 - sascha
@sascha：不确定您所指的简化是什么。至于二进制LP和ILS的比较，我找不到一个好的参考文献，但这两个似乎同意我的观点，即一般情况下二进制更容易解决：https://ai2-s2-pdfs.s3.amazonaws.com/8cb5/00820c7a42dd99327dd2cc49de9e6d6dba1f.pdf 和 https://www.researchgate.net/post/How_to_measure_the_difficulty_of_a_Mixed-Linear_Integer_Programming_MILP_problem - Ari
我同意链接2中前几条评论所说的一切。但这并不支持你的论点，就我所看到的而言。至于第一篇论文，虽然我很久以前读过几遍，但我懒得去查找你所说的那部分内容。在基于启发式优化的算法中，我们必须小心处理此类声明。另外：我们假设这里使用的是分支定界算法，而不是枚举算法，这当然会有所不同。 - sascha
@sascha：我指的是这句话：“一般整数变量通常比二进制变量难以解决”。还有：“这些情况可以从诸如对二进制变量进行探测（Savelsbergh，1994）或甚至专门算法的过程中获益。例如，二进制程序适合于文献中的一些已建立技术，如果算法在整数程序上执行，则不存在这些技术。这些技术包含在大多数标准分支限界优化器中；” - Ari
0
对每个手牌进行排序，删除重复值。删除任何一手牌中第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。
这能让你动起来吗？
- Prune
1
是的，我认为这是一个合理的方法，只要问题被限制在简单的例子中，但它不具有可扩展性。基本上是尝试所有组合，但带有一些限制条件。如果问题扩展到15个玩家，我认为我们会遇到问题。我正在尝试沿着网络分析或无监督聚类的方向思考，但我还没有想出任何可行的想法，这似乎是一个合理的方向。 - Chris.Caldwell
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接