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

References

• Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Let. 33(1):42–54.Crossref, Google Scholar
• Adjiman CS, Dallwig S, Floudas CA, Neumaier A (1998) A global optimization method, αBB, for general twice-differentiable constrained NLPs—I. Theoretical advances. Comput. Chemical Engrg. 22(9):1137–1158.Crossref, Google Scholar
• Agarwal A, Zhang T (2022) Minimax regret optimization for robust machine learning under distribution shift. 35th Annual Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 178 (PMLR, New York), 1–26..Google Scholar
• Akrotirianakis IG, Floudas CA (2004) A new class of improved convex underestimators for twice continuously differentiable constrained NLPs. J. Global Optim. 30:367–390.Crossref, Google Scholar
• Amemiya C, Alegria-Hartman M, Aslanidis C, Chen C, Nikolic J, Gingrich J, De Jong P (1992) A two-dimensional YAC pooling strategy for library screening via STS and Alu-PCR methods. Nucleic Acids Res. 20(10):2559–2563.Crossref, Google Scholar
• American Red Cross (2023) Details of tests performed for different infectious agents. Accessed October 18, 2023, https://www.redcrossblood.org/donate-blood/blood-donation-process/donation-process-overview.html.Google Scholar
• Aprahamian H, Bish DR, Bish EK (2016) Residual risk and waste in donated blood with pooled nucleic acid testing. Statist. Med. 35(28):5283–5301.Crossref, Google Scholar
• Aprahamian H, Bish EK, Bish DR (2018) Adaptive risk-based pooling in public health screening. IISE Trans. 50(9):753–766.Crossref, Google Scholar
• Aprahamian H, Bish DR, Bish EK (2019) Optimal risk-based group testing. Management Sci. 65(9):4365–4384.Link, Google Scholar
• Aprahamian H, Bish DR, Bish EK (2020a) Optimal group testing: Structural properties and robust solutions, with application to public health screening. INFORMS J. Comput. 32(4):895–911.Abstract, Google Scholar
• Aprahamian H, Bish EK, Bish DR (2020b) Static risk-based group testing schemes under imperfectly observable risk. Stochastic Systems 10(4):361–390.Link, Google Scholar
• Averbakh I, Berman O (2000) Minmax regret median location on a network under uncertainty. INFORMS J. Comput. 12(2):104–110.Link, Google Scholar
• Barillot E, Lacroix B, Cohen D (1991) Theoretical analysis of library screening using a n-dimensional pooling strategy. Nucleic Acids Res. 19(22):6241–6247.Crossref, Google Scholar
• Bateman AC, Mueller S, Guenther K, Shult P (2021) Assessing the dilution effect of specimen pooling on the sensitivity of SARS-CoV-2 PCR tests. J. Med. Virol. 93(3):1568–1572.Crossref, Google Scholar
• Bénichou M, Gauthier JM, Girodet P, Hentges G, Ribière G, Vincent O (1971) Experiments in mixed-integer linear programming. Math. Programming 1:76–94.Crossref, Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Crossref, Google Scholar
• Bilder CR, Iwen PC, Abdalhamid B, Tebbs JM, McMahan CS (2020) Tests in short supply? Try group testing. Significance 17(3):15.Crossref, Google Scholar
• Bish DR, Bish EK, El-Hajj H, Aprahamian H (2021) A robust pooled testing approach to expand COVID-19 screening capacity. PLoS One 16(2):e0246285.Crossref, Google Scholar
• Black MS, Bilder CR, Tebbs JM (2012) Group testing in heterogeneous populations by using halving algorithms. J. Roy. Statist. Soc. Ser. C Appl. Statist. 61(2):277–290.Crossref, Google Scholar
• Black MS, Bilder CR, Tebbs JM (2015) Optimal retesting configurations for hierarchical group testing. J. Roy. Statist. Soc. Ser. C Appl. Statist. 64(4):693–710.Crossref, Google Scholar
• Casado LG, Martínez J, García I (2001) Experiments with a new selection criterion in a fast interval optimization algorithm. J. Global Optim. 19:247–264.Crossref, Google Scholar
• Centers for Disease Control and Prevention (2021) CDC’s diagnostic test for COVID-19 only and supplies. Accessed June 12, 2021, https://stacks.cdc.gov/view/cdc/90576.Google Scholar
• Chatterjee S, Aprahamian H (2025) Capturing the dilution effect of risk-based grouping with application to COVID-19 screening. Naval Res. Logist. 72(1):24–44.Crossref, Google Scholar
• Csendes T (2001) New subinterval selection criteria for interval global optimization. J. Global Optim. 19(3):307–327.Crossref, Google Scholar
• Daumas M, Lester D, Munoz C (2009) Verified real number calculations: A library for interval arithmetic. IEEE Trans. Comput. 58(2):226–237.Crossref, Google Scholar
• Dawood H (2011) Theories of Interval Arithmetic: Mathematical Foundations and Applications (LAP Lambert Academic Publishing, London).Google Scholar
• Dorfman R (1943) The detection of defective members of large populations. Ann. Math. Statist. 14(4):436–440.Crossref, Google Scholar
• El-Amine H, Bish EK, Bish DR (2018) Robust postdonation blood screening under prevalence rate uncertainty. Oper. Res. 66(1):1–17.Link, Google Scholar
• El Ghaoui L, Lebret H (1997) Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Anal. Appl. 18(4):1035–1064.Crossref, Google Scholar
• European Blood Alliance (2013) Blood, tissues and cells from human origin. Accessed October 18, 2023, https://www.europeanbloodalliance.eu/wp-content/uploads/2013/04/eba_online.pdf.Google Scholar
• Finucan H (1964) The blood testing problem. J. Roy. Statist. Soc. Ser. C Appl. Statist. 13(1):43–50.Google Scholar
• Fredriksson A, Bokrantz R (2014) A critical evaluation of worst case optimization methods for robust intensity-modulated proton therapy planning. Med. Phys. 41(8):081701.Crossref, Google Scholar
• Gatera M, Bhatt S, Ngabo F, Utamuliza M, Sibomana H, Karema C, Mugeni C, et al. (2016) Successive introduction of four new vaccines in Rwanda: High coverage and rapid scale up of Rwanda’s expanded immunization program from 2009 to 2013. Vaccine 34(29):3420–3426.Crossref, Google Scholar
• Gounaris CE, Floudas CA (2008) Tight convex underestimators for C2-continuous problems: II. Multivariate functions. J. Global Optim. 42(1):69–89.Crossref, Google Scholar
• Gunantara N (2018) A review of multi-objective optimization: Methods and its applications. Cogent Engrg. 5(1):1502242.Crossref, Google Scholar
• Guzman YA, Hasan MF, Floudas CA (2014) Computational comparison of convex underestimators for use in a branch-and-bound global optimization framework. Rassias T, Floudas C, Butenko S, eds. Optimization in Science and Engineering: In Honor of the 60th Birthday of Panos M. Pardalos (Springer, New York), 229–246.Crossref, Google Scholar
• Hansen E (1965) Interval arithmetic in matrix computations, part I. J. Soc. Indust. Appl. Math. Ser. B Numer. Anal. 2(2):308–320.Crossref, Google Scholar
• Hasegawa R, Small D (2017) Sensitivity analysis for matched pair analysis of binary data: From worst case to average case analysis. Biometrics 73(4):1424–1432.Crossref, Google Scholar
• Hwang F (1975) A generalized binomial group testing problem. J. Amer. Statist. Assoc. 70(352):923–926.Crossref, Google Scholar
• Hwang F (1984) Robust group testing. J. Quality Tech. 16(4):189–195.Crossref, Google Scholar
• Hwang FK (1976) Group testing with a dilution effect. Biometrika 63(3):671–680.Crossref, Google Scholar
• Jiang H, Ahn H, Li X (2022) Group testing with consideration of the dilution effect. Mathematics 10(3):497.Crossref, Google Scholar
• Johnson NL, Kotz S, Wu XZ (1991) Inspection Errors for Attributes in Quality Control, vol. 44 (CRC Press, Boca Raton, FL).Crossref, Google Scholar
• Joyce JM (2012) Regret and instability in causal decision theory. Synthese 187:123–145.Crossref, Google Scholar
• Kennedy J, Eberhart R (1995) Particle swarm optimization. Proc. ICNN’95 Internat. Conf. Neural Networks, vol. 4 (IEEE, Piscataway, NJ), 1942–1948.Google Scholar
• Kim HY, Hudgens MG (2009) Three-dimensional array-based group testing algorithms. Biometrics 65(3):903–910.Crossref, Google Scholar
• Lasserre JB, Thanh TP (2013) Convex underestimators of polynomials. J. Global Optim. 56(1):1–25.Crossref, Google Scholar
• Levi R, Perakis G, Uichanco J (2011) Regret optimization for stochastic inventory models with spread. Working paper, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Li CH (1962) A sequential method for screening experimental variables. J. Amer. Statist. Assoc. 57(298):455–477.Crossref, Google Scholar
• Li S, Aprahamian H, Chatterjee S (2026) A convex relaxation-based spatial branching approach for optimal robust group testing designs under prevalence rate and dilution behavior uncertainty. https://doi.org/10.1287/ijoc.2023.0465.cd, https://github.com/INFORMSJoC/2023.0465.Google Scholar
• Loomes G, Sugden R (1982) Regret theory: An alternative theory of rational choice under uncertainty. Econom. J. 92(368):805–824.Google Scholar
• Maranas CD, Floudas CA (1994) A deterministic global optimization approach for molecular structure determination. J. Chem. Phys. 100(2):1247–1261.Crossref, Google Scholar
• Markót MC, Fernández J, Casado LG, Csendes T (2006) New interval methods for constrained global optimization. Math. Programming 106:287–318.Crossref, Google Scholar
• McMahan CS, Tebbs JM, Bilder CR (2013) Regression models for group testing data with pool dilution effects. Biostatistics 14(2):284–298.Crossref, Google Scholar
• Menachemi N, Collum TH (2011) Benefits and drawbacks of electronic health record systems. Risk Management Healthcare Policy 4:47–55.Crossref, Google Scholar
• Meyer CA, Floudas CA (2005) Convex underestimation of twice continuously differentiable functions by piecewise quadratic perturbation: Spline αBB underestimators. J. Global Optim. 32:221–258.Crossref, Google Scholar
• Michalewicz Z (2013) How to Solve It: Modern Heuristics (Springer Science & Business Media, Berlin, Heidelberg).Google Scholar
• Moré JJ (2006) The Levenberg-Marquardt algorithm: Implementation and theory. Watson GA, ed. Numer. Analysis: Proc. Biennial Conf. (Springer, Berlin, Heidelberg), 105–116.Google Scholar
• Morrison DR, Jacobson SH, Sauppe JJ, Sewell EC (2016) Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optim. 19:79–102.Crossref, Google Scholar
• Neveu B, Trombettoni G, Araya I (2016) Node selection strategies in interval branch and bound algorithms. J. Global Optim. 64:289–304.Crossref, Google Scholar
• Noh J, Danuser G (2021) Estimation of the fraction of COVID-19 infected people in U.S. states and countries worldwide. PLoS One 16(2):e0246772.Crossref, Google Scholar
• Perakis G, Roels G (2008) Regret in the newsvendor model with partial information. Oper. Res. 56(1):188–203.Link, Google Scholar
• Phatarfod R, Sudbury A (1994) The use of a square array scheme in blood testing. Statist. Med. 13(22):2337–2343.Crossref, Google Scholar
• Reason J (2000) Human error: Models and management. BMJ 320(7237):768–770.Crossref, Google Scholar
• Shahriari B, Swersky K, Wang Z, Adams RP, De Freitas N (2016) Taking the human out of the loop: A review of Bayesian optimization. Proc. IEEE 104(1):148–175.Crossref, Google Scholar
• Skjäl A, Westerlund T (2014) New methods for calculating αBB-type underestimators. J. Global Optim. 58(3):411–427.Crossref, Google Scholar
• Skjäl A, Westerlund T, Misener R, Floudas CA (2012) A generalization of the classical αBB convex underestimation via diagonal and nondiagonal quadratic terms. J. Optim. Theory Appl. 154:462–490.Crossref, Google Scholar
• Sobel M, Groll PA (1959) Group testing to eliminate efficiently all defectives in a binomial sample. Bell System Tech. J. 38(5):1179–1252.Crossref, Google Scholar
• Spivak M (1994) Calculus, 3rd ed. (Publish or Perish, Houston).Google Scholar
• Sterrett A (1957) On the detection of defective members of large populations. Ann. Math. Statist. 28(4):1033–1036.Crossref, Google Scholar
• Tan CK, Sim ML, Chuah TC (2008) Game theoretic approach for channel assignment and power control with no-internal-regret learning in wireless ad hoc networks. IET Comm. 2(9):1159–1169.Crossref, Google Scholar
• Tebbs JM, McMahan CS, Bilder CR (2013) Two-stage hierarchical group testing for multiple infections with application to the infertility prevention project. Biometrics 69(4):1064–1073.Crossref, Google Scholar
• Wein LM, Zenios SA (1996) Pooled testing for HIV screening: Capturing the dilution effect. Oper. Res. 44(4):543–569.Link, Google Scholar