{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T00:12:03Z","timestamp":1744157523453,"version":"3.28.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,7,29]],"date-time":"2023-07-29T00:00:00Z","timestamp":1690588800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,29]],"date-time":"2023-07-29T00:00:00Z","timestamp":1690588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Medical Research Council","award":["MR\/V038591\/1","MR\/V038591\/1"],"award-info":[{"award-number":["MR\/V038591\/1","MR\/V038591\/1"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Stat Comput"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We show how combinatorial optimisation algorithms can be applied to the problem of identifying c-optimal experimental designs when there may be correlation between and within experimental units and evaluate the performance of relevant algorithms. We assume the data generating process is a generalised linear mixed model and show that the c-optimal design criterion is a monotone supermodular function amenable to a set of simple minimisation algorithms. We evaluate the performance of three relevant algorithms: the local search, the greedy search, and the reverse greedy search. We show that the local and reverse greedy searches provide comparable performance with the worst design outputs having variance<jats:inline-formula><jats:alternatives><jats:tex-math>$$&lt;10\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>&lt;<\/mml:mo><mml:mn>10<\/mml:mn><mml:mo>%<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>greater than the best design, across a range of covariance structures. We show that these algorithms perform as well or better than multiplicative methods that generate weights to place on experimental units. We extend these algorithms to identifying modle-robust c-optimal designs.<\/jats:p>","DOI":"10.1007\/s11222-023-10280-w","type":"journal-article","created":{"date-parts":[[2023,7,29]],"date-time":"2023-07-29T16:01:50Z","timestamp":1690646510000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Evaluation of combinatorial optimisation algorithms for c-optimal experimental designs with correlated observations"],"prefix":"10.1007","volume":"33","author":[{"given":"Samuel I.","family":"Watson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Pan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,29]]},"reference":[{"key":"10280_CR1","volume-title":"Fair Representation: Meeting the Ideal of One Man, One Vote","author":"M Balinski","year":"2002","unstructured":"Balinski, M., Young, P.: Fair Representation: Meeting the Ideal of One Man, One Vote, 2nd edn. Brookings Institution Press, Washington (2002)","edition":"2"},{"issue":"421","key":"10280_CR2","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/01621459.1993.10594284","volume":"88","author":"NE Breslow","year":"1993","unstructured":"Breslow, N.E., Clayton, D.G.: Approximate inference in generalized linear mixed models. J. Am. Stat. Assoc. 88(421), 9\u201325 (1993). https:\/\/doi.org\/10.1080\/01621459.1993.10594284","journal-title":"J. Am. Stat. Assoc."},{"key":"10280_CR3","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1214\/ss\/1177009939","volume":"10","author":"K Chaloner","year":"1995","unstructured":"Chaloner, K., Verdinelli, I.: Bayesian experimental design: a review. Stat. Sci. 10, 273\u2013304 (1995)","journal-title":"Stat. Sci."},{"issue":"1","key":"10280_CR4","doi-asserted-by":"publisher","DOI":"10.1002\/env.2425","volume":"28","author":"M Chipeta","year":"2017","unstructured":"Chipeta, M., Terlouw, D., Phiri, K., Diggle, P.: Inhibitory geostatistical designs for spatial prediction taking account of uncertain covariance structure. Environmetrics 28(1), e2425 (2017). https:\/\/doi.org\/10.1002\/env.2425","journal-title":"Environmetrics"},{"key":"10280_CR5","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349149.full","author":"H Dette","year":"1993","unstructured":"Dette, H.: Elfving\u2019s theorem for \\$D\\$-optimality. Ann. Stat. (1993). https:\/\/doi.org\/10.1214\/aos\/1176349149.full","journal-title":"Ann. Stat."},{"issue":"Part 3","key":"10280_CR6","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1111\/1467-9876.00113","volume":"47","author":"PJ Diggle","year":"1998","unstructured":"Diggle, P.J., Tawn, J.A., Moyeed, R.A.: Model-based geostatistics (with discussion). J. R. Stat. Soc. Ser. C 47(Part 3), 299\u2013350 (1998)","journal-title":"J. R. Stat. Soc. Ser. C"},{"issue":"2","key":"10280_CR7","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1214\/aoms\/1177729442","volume":"23","author":"G Elfving","year":"1952","unstructured":"Elfving, G.: Optimum allocation in linear regression theory. Ann. Math. Stat. 23(2), 255\u2013262 (1952)","journal-title":"Ann. Math. Stat."},{"key":"10280_CR8","volume-title":"Theory of Optimal Experiments","author":"V Fedorov","year":"1972","unstructured":"Fedorov, V.: Theory of Optimal Experiments. Academic Press, New York (1972)"},{"issue":"4","key":"10280_CR9","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998). https:\/\/doi.org\/10.1145\/285055.285059","journal-title":"J. ACM"},{"issue":"2","key":"10280_CR10","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/130920277","volume":"43","author":"Y Filmus","year":"2014","unstructured":"Filmus, Y., Ward, J.: Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43(2), 514\u2013542 (2014). https:\/\/doi.org\/10.1137\/130920277","journal-title":"SIAM J. Comput."},{"key":"10280_CR11","doi-asserted-by":"crossref","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions-II. In: Polyhedral Combinatorics. Mathematical Programming Studies, vol. 8. Springer (1978)","DOI":"10.1007\/BFb0121195"},{"key":"10280_CR12","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1111\/j.2517-6161.1992.tb01897.x","volume":"54","author":"I Ford","year":"1992","unstructured":"Ford, I., Torsney, B., Wu, C.F.J.: The use of a canonical form in the construction of locally optimal designs for non-linear problems. J. R. Stat. Soc. Ser. B (Methodol.) 54, 569\u2013583 (1992)","journal-title":"J. R. Stat. Soc. Ser. B (Methodol.)"},{"issue":"13","key":"10280_CR13","doi-asserted-by":"publisher","first-page":"2149","DOI":"10.1002\/sim.6850","volume":"35","author":"AJ Girling","year":"2016","unstructured":"Girling, A.J., Hemming, K.: Statistical efficiency and optimal design for stepped cluster studies under linear mixed effects models. Stat. Med. 35(13), 2149\u20132166 (2016). https:\/\/doi.org\/10.1002\/sim.6850","journal-title":"Stat. Med."},{"key":"10280_CR14","doi-asserted-by":"publisher","unstructured":"Guo, Y., Dy, J., Erdogmus, D., Kalpathy-Cramer, J., Ostmo, S., Campbell, J.P., Chiang, M.F., Ioannidis, S.: Accelerated experimental design for pairwise comparisons. In: Proceedings of the 2019 SIAM International Conference on Data Mining\u2019, Society for Industrial and Applied Mathematics, Philadelphia, PA, pp.\u00a0432\u2013440 (2019). https:\/\/doi.org\/10.1137\/1.9781611975673.49","DOI":"10.1137\/1.9781611975673.49"},{"issue":"2","key":"10280_CR15","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.csda.2008.06.023","volume":"53","author":"R Harman","year":"2008","unstructured":"Harman, R., Jur\u00edk, T.: Computing -optimal experimental designs using the simplex method of linear programming. Comput. Stat. Data Anal. 53(2), 247\u2013254 (2008)","journal-title":"Comput. Stat. Data Anal."},{"key":"10280_CR16","doi-asserted-by":"publisher","DOI":"10.1093\/ije\/dyz237\/5748155","author":"K Hemming","year":"2020","unstructured":"Hemming, K., Kasza, J., Hooper, R., Forbes, A., Taljaard, M.: A tutorial on sample size calculation for multiple-period cluster randomized parallel, cross-over and stepped-wedge trials using the Shiny CRT calculator. Int. J. Epidemiol. (2020). https:\/\/doi.org\/10.1093\/ije\/dyz237\/5748155","journal-title":"Int. J. Epidemiol."},{"key":"10280_CR17","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1002\/sim.6325","volume":"34","author":"K Hemming","year":"2015","unstructured":"Hemming, K., Lilford, R., Girling, A.J.: Stepped-wedge cluster randomised controlled trials: a generic framework including parallel and multiple-level designs. Stat. Med. 34, 181\u2013196 (2015). https:\/\/doi.org\/10.1002\/sim.6325","journal-title":"Stat. Med."},{"issue":"2","key":"10280_CR18","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1111\/j.1467-9868.2010.00757.x","volume":"73","author":"T Holland-Letz","year":"2011","unstructured":"Holland-Letz, T., Dette, H., Pepelyshev, A.: A geometric characterization of optimal designs for regression models with correlated observations. J. Stat. Soc. Ser. B (Stat. Methodol.) 73(2), 239\u2013252 (2011). https:\/\/doi.org\/10.1111\/j.1467-9868.2010.00757.x","journal-title":"J. Stat. Soc. Ser. B (Stat. Methodol.)"},{"key":"10280_CR19","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1111\/j.1541-0420.2011.01657.x","volume":"68","author":"T Holland-Letz","year":"2012","unstructured":"Holland-Letz, T., Dette, H., Renard, D.: Efficient algorithms for optimal designs with correlated observations in pharmacokinetics and dose-finding studies. Biometrics 68, 138\u2013145 (2012)","journal-title":"Biometrics"},{"issue":"1","key":"10280_CR20","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1186\/s12874-020-01155-z","volume":"20","author":"R Hooper","year":"2020","unstructured":"Hooper, R., Kasza, J., Forbes, A.: The hunt for efficient, incomplete designs for stepped wedge trials with continuous recruitment and continuous outcome measures. BMC Med. Res. Methodol. 20(1), 279 (2020). https:\/\/doi.org\/10.1186\/s12874-020-01155-z","journal-title":"BMC Med. Res. Methodol."},{"issue":"2","key":"10280_CR21","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/j.cct.2006.05.007","volume":"28","author":"MA Hussey","year":"2007","unstructured":"Hussey, M.A., Hughes, J.P.: Design and analysis of stepped wedge cluster randomized trials. Contemp. Clin. Trials 28(2), 182\u2013191 (2007)","journal-title":"Contemp. Clin. Trials"},{"issue":"1\u20133","key":"10280_CR22","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0166-218X(00)00366-8","volume":"114","author":"VP Il\u2019ev","year":"2001","unstructured":"Il\u2019ev, V.P.: An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function. Discrete Appl. Math. 114(1\u20133), 131\u2013146 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"10280_CR23","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1111\/biom.12959","volume":"75","author":"J Kasza","year":"2019","unstructured":"Kasza, J., Forbes, A.B.: Information content of cluster-period cells in stepped wedge trials. Biometrics 75(1), 144\u2013152 (2019). https:\/\/doi.org\/10.1111\/biom.12959","journal-title":"Biometrics"},{"issue":"2","key":"10280_CR24","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1177\/0962280220932962","volume":"30","author":"F Li","year":"2021","unstructured":"Li, F., Hughes, J.P., Hemming, K., Taljaard, M., Melnick, E.R., Heagerty, P.J.: Mixed-effects models for the design and analysis of stepped wedge cluster randomized trials: an overview. Stat. Methods Med. Res. 30(2), 612\u2013639 (2021). https:\/\/doi.org\/10.1177\/0962280220932962","journal-title":"Stat. Methods Med. Res."},{"key":"10280_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-3242-6","volume-title":"Generalized Linear Models","author":"P McCullagh","year":"1989","unstructured":"McCullagh, P., Nelder, J.A.: Generalized Linear Models, 2nd edn. Routledge, London (1989)","edition":"2"},{"issue":"2","key":"10280_CR26","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1093\/biomet\/90.2.423","volume":"90","author":"WG Muller","year":"2003","unstructured":"Muller, W.G., P\u00e1zman, A.: Measures for designs in experiments with correlated errors. Biometrika 90(2), 423\u2013434 (2003). https:\/\/doi.org\/10.1093\/biomet\/90.2.423","journal-title":"Biometrika"},{"issue":"4","key":"10280_CR27","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1080\/02331888508801879","volume":"16","author":"W N\u00e4ther","year":"1985","unstructured":"N\u00e4ther, W.: Exact designs for regression models with correlated errors. Statistics 16(4), 479\u2013484 (1985). https:\/\/doi.org\/10.1080\/02331888508801879","journal-title":"Statistics"},{"issue":"3","key":"10280_CR28","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177\u2013188 (1978). https:\/\/doi.org\/10.1287\/moor.3.3.177","journal-title":"Math. Oper. Res."},{"issue":"4","key":"10280_CR29","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1016\/0167-9473(92)90064-M","volume":"14","author":"N-K Nguyen","year":"1992","unstructured":"Nguyen, N.-K., Miller, A.J.: A review of some exchange algorithms for constructing discrete D-optimal designs. Comput. Stat. Data Anal. 14(4), 489\u2013498 (1992)","journal-title":"Comput. Stat. Data Anal."},{"issue":"4","key":"10280_CR30","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1080\/00401706.2016.1251495","volume":"59","author":"AM Overstall","year":"2017","unstructured":"Overstall, A.M., Woods, D.C.: Bayesian design of experiments using approximate coordinate exchange. Technometrics 59(4), 458\u2013470 (2017). https:\/\/doi.org\/10.1080\/00401706.2016.1251495","journal-title":"Technometrics"},{"key":"10280_CR31","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0378-3758(80)90020-8","volume":"4","author":"F Pukelsheim","year":"1980","unstructured":"Pukelsheim, F.: On linear regression designs which maximize information. J. Stat. Plan. Inference 4, 339\u2013364 (1980)","journal-title":"J. Stat. Plan. Inference"},{"issue":"4","key":"10280_CR32","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1093\/biomet\/79.4.763","volume":"79","author":"F Pukelsheim","year":"1992","unstructured":"Pukelsheim, F., Rieder, S.: Efficient rounding of approximate designs. Biometrika 79(4), 763 (1992)","journal-title":"Biometrika"},{"issue":"2","key":"10280_CR33","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/0910022","volume":"10","author":"TG Robertazzi","year":"1989","unstructured":"Robertazzi, T.G., Schwartz, S.C.: An accelerated sequential algorithm for producing D-optimal designs. SIAM J. Sci. Stat. Comput. 10(2), 341\u2013358 (1989). https:\/\/doi.org\/10.1137\/0910022","journal-title":"SIAM J. Sci. Stat. Comput."},{"issue":"1","key":"10280_CR34","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1214\/aoms\/1177698504","volume":"39","author":"J Sacks","year":"1968","unstructured":"Sacks, J., Ylvisaker, D.: Designs for regression problems with correlated errors: many parameters. Ann. Math. Stat. 39(1), 49\u201369 (1968)","journal-title":"Ann. Math. Stat."},{"issue":"5","key":"10280_CR35","doi-asserted-by":"publisher","first-page":"1684","DOI":"10.1016\/j.jspi.2010.11.031","volume":"141","author":"G Sagnol","year":"2011","unstructured":"Sagnol, G.: Computing optimal designs of multiresponse experiments reduces to second-order cone programming. J. Stat. Plan. Inference 141(5), 1684\u20131708 (2011)","journal-title":"J. Stat. Plan. Inference"},{"issue":"1\u20132","key":"10280_CR36","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jspi.2003.05.004","volume":"130","author":"W Studden","year":"2005","unstructured":"Studden, W.: Elfving\u2019s theorem revisited. J. Stat. Plan. Inference 130(1\u20132), 85\u201394 (2005)","journal-title":"J. Stat. Plan. Inference"},{"issue":"4","key":"10280_CR37","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1287\/moor.2016.0842","volume":"42","author":"M Sviridenko","year":"2017","unstructured":"Sviridenko, M., Vondr\u00e1k, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4), 1197\u20131218 (2017). https:\/\/doi.org\/10.1287\/moor.2016.0842","journal-title":"Math. Oper. Res."},{"issue":"3","key":"10280_CR38","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1093\/biomet\/asv005","volume":"102","author":"TW Waite","year":"2015","unstructured":"Waite, T.W., Woods, D.C.: Designs for generalized linear models with random block effects via information matrix approximations. Biometrika 102(3), 677\u2013693 (2015)","journal-title":"Biometrika"},{"issue":"14","key":"10280_CR39","doi-asserted-by":"publisher","first-page":"3158","DOI":"10.3390\/s19143158","volume":"19","author":"J Yang","year":"2019","unstructured":"Yang, J., Ban, X., Xing, C.: Using greedy random adaptive procedure to solve the user selection problem in mobile crowdsourcing. Sensors 19(14), 3158 (2019)","journal-title":"Sensors"},{"issue":"504","key":"10280_CR40","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1080\/01621459.2013.806268","volume":"108","author":"M Yang","year":"2013","unstructured":"Yang, M., Biedermann, S., Tang, E.: On optimal designs for nonlinear models: a general and efficient algorithm. J. Am. Stat. Assoc. 108(504), 1411\u20131420 (2013). https:\/\/doi.org\/10.1080\/01621459.2013.806268","journal-title":"J. Am. Stat. Assoc."},{"key":"10280_CR41","doi-asserted-by":"publisher","unstructured":"Yu, Y.: D-optimal designs via a cocktail algorithm. Stat. Comput. 21(4), 475\u2013481 (2011). https:\/\/doi.org\/10.1007\/s11222-010-9183-2","DOI":"10.1007\/s11222-010-9183-2"},{"issue":"4","key":"10280_CR42","doi-asserted-by":"publisher","first-page":"1049","DOI":"10.2307\/2531734","volume":"44","author":"SL Zeger","year":"1988","unstructured":"Zeger, S.L., Liang, K.-Y., Albert, P.S.: Models for longitudinal data: a generalized estimating equation approach. Biometrics 44(4), 1049\u20131060 (1988)","journal-title":"Biometrics"},{"issue":"2","key":"10280_CR43","doi-asserted-by":"publisher","first-page":"7256396","DOI":"10.1155\/2016\/7256396","volume":"12","author":"Z-Q Zou","year":"2016","unstructured":"Zou, Z.-Q., Li, Z.-T., Shen, S., Wang, R.-C.: Energy-efficient data recovery via greedy algorithm for wireless sensor networks. Int. J. Distrib. Sens. Netw. 12(2), 7256396 (2016). https:\/\/doi.org\/10.1155\/2016\/7256396","journal-title":"Int. J. Distrib. Sens. Netw."}],"container-title":["Statistics and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-023-10280-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11222-023-10280-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-023-10280-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T08:53:39Z","timestamp":1729846419000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11222-023-10280-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,29]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["10280"],"URL":"https:\/\/doi.org\/10.1007\/s11222-023-10280-w","relation":{},"ISSN":["0960-3174","1573-1375"],"issn-type":[{"type":"print","value":"0960-3174"},{"type":"electronic","value":"1573-1375"}],"subject":[],"published":{"date-parts":[[2023,7,29]]},"assertion":[{"value":"19 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"112"}}