Optimal Screening of Populations with Heterogeneous Risk Profiles Under the Availability of Multiple Tests

We study the design of large-scale group testing schemes under a heterogeneous population (i.e., subjects with potentially different risk) and with the availability of multiple tests. The objective is to classify the population as positive or negative for a given binary characteristic (e.g., the presence of an infectious disease) as efficiently and accurately as possible. Our approach examines components often neglected in the literature, such as the dependence of testing cost on the group size and the possibility of no testing, which are especially relevant within a heterogeneous setting. By developing key structural properties of the resulting optimization problem, we are able to reduce it to a network flow problem under a specific, yet not too restrictive, objective function. We then provide results that facilitate the construction of the resulting graph and finally provide a polynomial time algorithm. Our case study, on the screening of HIV in the United States, demonstrates the substantial benefits of the proposed approach over conventional screening methods. Summary of Contribution: This paper studies the problem of testing heterogeneous populations in groups in order to reduce costs and hence allow for the use of more efficient tests for high-risk groups. The resulting problem is a difficult combinatorial optimization problem that is NP-complete under a general objective. Using structural properties specific to our objective function, we show that the problem can be cast as a network flow problem and provide a polynomial time algorithm.