-1

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).

4

2 回答 2

0

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

\sum_j x_j.A_ij >= 1 forall i
于 2012-04-11T10:40:52.003 回答
-1

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

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

观察那两行kl是相同的当且仅当(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 <= m1 <= l <= 1这样的k != l

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

于 2012-04-13T20:50:44.193 回答