Robust Group Testing

Abstract

Group testing enjoys wide application in the medical diagnosis, compressed sensing and telecommunication. It becomes very popular during the COVID pandemic where test item size is too large to carry out individual testing over each item within the short time period. The main purpose of group testing problem is to minimize the test numbers in detecting defective and nondetective items by designing the corresponding group testing plan. Although there is abundant work on detecting items based on the prescribed test groups, to our best knowledge, the optimization approach to joint group design and testing is limited. In addition, there are numerous uncertainties of the unknown state of items. Thus, we propose a two-stage robust optimization approach to quantifying the uncertainties involved in jointly designing groups and testing items. More specifically, in our second stage problem where we conduct individual testing over items that have not been detected, we build a robust integer optimization model based on a finite scenario uncertainty set of unknown test item states. Furthermore, we develop two methods for solving this model. The first one is a binary programming approach based on lifting the two-stage model with an epigraphical variable. The second one is the Benders’ decomposition method because the linear programming relaxation of the second-stage problem with integer variables is tight. Finally, we numerically compare the performances of these two methods under various parameter regimes and uncertainty sets in terms of their computational efficiency.