找到使每行总和最小值最大化的列集

Question

给定一个矩阵 A，我正在寻找 p 列的集合，该组最大化每行中匹配单元格总和的最小值。

例如：如果 p=2 且 A=

1 2 4

3 0 3

5 6 2

选择 C1 和 C2 将给出 f=min(r1,r2,r3)=min(1+2; 3+0; 5+6) =3

当选择C1和C3时，f=min(1+4; 3+3; 5+2)=5，这是最好的选择。

有没有任何算法或启发式这样做..

谢谢

Answer 1

这个问题是 NP 困难的，通过对集合覆盖进行简单的简化（令 A 为表示元素集包含关系的 0-1 矩阵）。我会在简单的整数规划公式上尝试 MIP 求解器，其中如果采用第 j 列，则 c(j) 为 1，否则为 0。

maximize lambda
subject to
lambda <= c(1) A(i,1) + ... + c(n) A(i,n)    for all i
c(1) + ... + c(n) = p
c(j) in {0, 1}                               for all j