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

Question

假设我有一个 (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 上的第一篇文章，所以如果我在某个地方失礼了，请对我温柔点!

(如果有兴趣，我也有 asked the same question on Math Stack Exchange ，但在那里我不太关心算法效率，更关心数学技巧。)

Answer 1

我的第一次尝试是 integer-programming使用可用的高性能求解器之一(例如 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

也许可以通过额外的不等式(例如派系不等式(冲突图 -> 最大派系))来加强这个公式，但不确定这是否有帮助。好的求解器会动态执行类似的操作，生成切割。

有很多理论可供引用。一个关键字是 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

备注:

• 代码使用了cvxpy，它非常强大，但缺乏一些高级整数编程支持
  • 唯一易于使用的非商业求解器是 GLPK，它非常好，但通常无法与 Cbc 竞争
  • cvxpy 的代数用法与一些接口(interface)决策一起导致了这里不寻常的变量边界作为约束公式