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
n
xn
matrixA
whereA[i][j]
is a binary value representing the result of running thej
th test on a patient with the thei
th 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).