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

Question

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

示例问题:3 个人各有一手牌。每只手都包含一个独特的集合，但 3 个集合可能会重叠。每个玩家可以挑选三张牌贡献给中间。我怎样才能最大化 9 张贡献卡片的总和

• 每位玩家刚好贡献 3 张牌
• 所有 9 张卡片都是独一无二的(如果可能)
• 可在 200 张可能的“卡片”、40 张范围内扩展的解决方案贡献者和 6 个贡献者。

Answer 1

整数规划听起来是一种可行的方法。在没有保证的情况下，这个问题也感觉 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 风格的基于惩罚的目标:例如最大化(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]