linear-programming - Integer Linear Programming formulation for Test Cover?

Question

The Test Cover problem can be defined as follows:

Suppose we have a set of n diseases and a set of m tests we can perform to check for symptoms. We also are given the following:

• an nxn matrix A where A[i][j] is a binary value representing the result of running the jth test on a patient with the the ith disease (1 indicates a positive result, 0 indicates negative);
• the cost of running test j, c_j; and that
• any patient will have exactly one disease

The task is to find a set of tests that can uniquely identify each of the the n diseases at minimal cost.

---

This problem can be formulated as an Integer Linear Program, where we want to minimize the objective function \sum_{j=1}^{m} c_j x_j, where x_j = 1 if we choose to include test j in our set, and 0 otherwise.

My question is:

What is the set of linear constraints for this problem?

Incidentally, I believe this problem is NP-hard (as is Integer Linear Programming in general).

Answer 1

好吧，如果我是正确的，您只需要确保

\sum_j x_j.A_ij >= 1 forall i

Answer 2

让我们T删除所有这样= 0的j第 th 列的矩阵。Ajx_j

那么选择一组能够唯一区分任意两种疾病的测试，就相当于保证每一行T都是唯一的。

观察那两行k和l是相同的当且仅当(T[k][j] XOR T[l][j]) = 0对于 all j。

所以，我们想要的约束是

\sum_{j=1}^{m} x_j(A[k][j] XOR A[l][j]) >= 1

对于所有1 <= k <= m和1 <= l <= 1这样的k != l。

请注意，上面的约束是线性的，因为我们可以预先计算系数(A[k][j] XOR A[l][j])。