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

Hrayer Aprahamian () and Hadi El-Amine ()
Additional contact information
Hrayer Aprahamian: Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas 77843
Hadi El-Amine: Department of Systems Engineering and Operations Research, George Mason University, Fairfax, Virginia 22030

INFORMS Journal on Computing, 2022, vol. 34, issue 1, 150-164

Abstract: 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.

Keywords: group testing; heterogeneous population; multiple tests; network flow; polynomial time algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1051 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:1:p:150-164

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().