algorithm - 找到使每行中的和最小的列集

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 求解器，如果取第 th 列，c(j)则为 1 ，否则为 0。j

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