Optimal Group Testing: Structural Properties and Robust Solutions, with Application to Public Health Screening

We provide a novel regret-based robust formulation of the Dorfman group size problem considering the realistic setting where the prevalence rate is uncertain, establish key structural properties of the optimal solution, and provide an exact algorithm. Our analysis also leads to exact closed-form expressions for the optimal Dorfman group size under a deterministic prevalence rate, which is the problem studied in the extant literature. Thus, our structural results not only unify existing, and mostly empirical, results on the Dorfman group size problem under a deterministic prevalence rate, but, more importantly, enable us to efficiently solve the robust version of this problem to optimality. We demonstrate the value of robust testing schemes with a case study on disease screening using realistic data. Our case study indicates that robust testing schemes can significantly outperform their deterministic counterparts, by not only substantially reducing the maximum regret value, but, in the majority of the cases, reducing testing costs as well. Our findings have important implications on public health screening practices.