Two-Stage Stochastic and Robust Optimization for Non-Adaptive Group Testing

Abstract

We consider the problem of detecting defective items amongst a large collection, by conducting tests of individual or groups of items. Group testing offers improvements over the naive individual testing scheme by potentially certifying multiple individual items as non-defective with a single test. The group testing problem aims to design a group testing plan to detect the defective items using as few tests as possible. We propose novel two-stage stochastic and robust optimization formulations for the design of group testing plans in the noiseless non-adaptive setting. Our formulations enable us to certify optimality for existing group testing schemes, as well as model complex grouping constraints, a feature that is not discussed in the existing literature.