快速算法，精确查找二元矩阵中的 k 列，使这些列的总和为 1-向量

假设我有一个 (M x N) 二进制矩阵，其中 M 和 N 都可以很大。我想精确地找到 k 列（k 相对较小，比如小于 10），这样这 k 列的总和就是 1 向量（所有元素均为 1）。一种解决方案就足够了。有没有快速的算法？

例如，处理矩阵的算法

1 0 0
1 0 0
1 1 0
0 1 1

k=2 时应返回第 0 列和第 2 列，但如果 k=1 或 k=3 则不应报告任何解。

我尝试过两种方法：

1. 慢速组合方法，我尝试所有（N 选择 k）组合并找到总和为 1-向量的组合。这需要 O(N^k) 时间，这显然是可怕的。
2. 递归方法，速度更快，但在最坏情况下仍然需要 O(N^k) 时间。 Python代码如下：

import numpy as np

def recursiveFn(mat, col_used_bool, col_sum_to_date, cols_to_go):
    N = len(mat)
    if cols_to_go == 1:
        col_unused = 1 - col_sum_to_date
        if list(col_unused) in [list(i) for i in mat]:
            return (True, [col_unused])
        else:
            return (False, None)
    for col_id in range(N):
        if col_used_bool[col_id]:
            continue
        if 2 not in mat[col_id]+col_sum_to_date:
            col_used_bool[col_id] = True
            x = recursiveFn(mat, col_used_bool, mat[col_id]+col_sum_to_date, cols_to_go-1)
            col_used_bool[col_id] = False
            if x[0]:
                return (True, x[1] + [mat[col_id]])
    return (False, None)

exMat = [[1,1,1,0],[0,0,1,1],[0,0,0,1]] #input by colums
exMat = [np.asarray(i) for i in exMat]
k = 2
output = recursiveFn(mat = exMat, col_used_bool = [False for i in exMat], 
    col_sum_to_date = np.asarray([0 for i in exMat[0]]), cols_to_go = k)
print(output[1])
### prints this : [array([0, 0, 0, 1]), array([1, 1, 1, 0])]

我对这两种方法都不满意，我觉得存在更智能、更快的算法。非常感谢您的帮助。这是我在 StackOverflow 上的第一篇文章，所以如果我在某个地方失礼了，请对我温和一些！

（如果有兴趣的话我也在 Math Stack Exchange 上问了同样的问题 https://math.stackexchange.com/q/3727899/801803，但我不太关心算法效率，而更关心数学技巧。）

我的第一次尝试是整数规划 https://en.wikipedia.org/wiki/Integer_programming使用可用的高性能求解器之一（例如Cbc https://github.com/coin-or/Cbc).

假设一些稀疏性在你的发生矩阵中，这些将非常有效并且非常普遍（侧面约束/适应）。它们也是完整的，并且可能能够证明不可行。

一个简单的公式如下：

Instance

c0 c1 c2
1  0  0  r0
1  0  0  r1
1  1  0  r2
0  1  1  r3

IP:

minimize(0)        # constant objective | pure feasibility problem

sum(c_i) = k       # target of columns chosen

r0 = 1 = c0        # r0 just showing the origin of the constraint; no real variable!
r1 = 1 = c0
r2 = 1 = c0 + c1
r3 = 1 = c1 + c2

c_i in {0, 1}      # all variables are binary

也许可以通过额外的不等式（例如派系不等式（冲突图 -> 最大派系））来加强这个公式，但不确定这是否有帮助。好的求解器会做类似的事情动态地正在生成cuts.

有很多理论可供参考。一个关键字是精确覆盖 https://en.wikipedia.org/wiki/Exact_cover或所有非常相似的包装/覆盖问题。

简单的代码示例：

import cvxpy as cp
import numpy as np

data = np.array([[1, 0, 0],
                 [1, 0, 0],
                 [1, 1, 0],
                 [0, 1, 1]])

def solve(k, data):
  c = cp.Variable(data.shape[1], boolean=True)

  con = [data * c == 1,
         cp.sum(c) == k,
         c >= 0,
         c <= 1]

  obj = cp.Minimize(0)
  
  problem = cp.Problem(obj, con)
  problem.solve(verbose=True, solver=cp.GLPK_MI)

  if(problem.status == 'optimal'):
    return np.where(np.isclose(c.value, 1.0) == True)[0]
  else:
    assert problem.status == 'infeasible'
    return None

print(solve(2, data))
print(solve(1, data))
print(solve(3, data))

# [0 2]
# None
# None

Remarks:

• The code uses cvxpy which is very powerful, but lacks some advanced integer-programming support
  • 唯一易于使用的非商业求解器是GLPK，这非常好，但通常无法与Cbc
  • cvxpy 的代数用法与一些接口决策一起导致不寻常的变量边界作为约束此处表述