A Convex Relaxation-Based Spatial Branching Approach for Optimal Robust Group Testing Designs Under Prevalence Rate and Dilution Behavior Uncertainty

Group testing is a widely adopted strategy for screening large populations for infectious diseases. Its efficiency is heavily influenced by the prevalence rate and the dilution effect of pooling, a phenomenon in which test accuracy deteriorates for large group sizes. Both factors are highly uncertain, motivating the need for robust testing schemes. In this paper, we introduce a novel regret-based formulation of the Dorfman group testing problem that accounts for uncertainty in both the prevalence rate and the dilution behavior of the assay. To solve the resulting minimax regret problem, we recast it as a more tractable conventional minimax problem and solve the nonconvex reformulation via spatial branching with convex relaxations. We derive theoretical properties for efficiently constructing convex underestimators that are guaranteed to converge to the original objective and use these to prove the algorithm’s convergence to an [Formula: see text]-optimal solution. A case study on COVID-19 with real clinical data demonstrates the algorithm’s efficiency and shows that robust testing schemes reduce maximum regret while improving both testing costs and classification accuracy. History: Accepted by J. Paul Brooks, Area Editor for Applications in Biology, Medicine, & Healthcare. Funding: This material is based on work supported in part by the National Science Foundation [Grant 2414715]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0465 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0465 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .