线性规划问题，寻找具有最多共同点的组

Question

我有 6 个带有二进制变量的数字矩阵，如下所示：

matrix 1:[0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1]
matrix 2:[0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1]
matrix 3:[0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1]
matrix 4:[1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1]
matrix 5:[1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]
matrix 6:[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1]

我想知道线性规划中是否有一种方法可以找到三个矩阵中哪些矩阵的共同点最多。

所以在这种情况下，它可能会分组 4,5 和 6，因为它们有 10 个共同点：

[1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1]

我想不出一个解决方案来让我们说行话找到所有三组并给我最好的一组。

任何帮助将不胜感激，我愿意给予经济回报。 顺便说一句：抱歉我的英语不好。

Answer 1

让：

    i : rows
    j : columns
    d[i,j] : data matrix
    M : number of columns (21 in your example)
    k : number of rows that should match (k=3)
   

定义以下变量：

   binary variable pattern[j]  
   integer variable diff[i]  (differences wrt pattern in row i)
   binary variable ok[i]     (ok[i]=1 => diff[i]=0)

型号：

   max sum(j,pattern[j])
   subject to
       sum(j,d[i,j]*pattern[j]) + diff[i] = sum(j,sub[j])   forall i
       diff[i] <= (1-ok[i])*M                               forall i
       sum(i, ok[i]) >= k