{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T14:10:04Z","timestamp":1726323004614},"reference-count":69,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2021,12,15]],"date-time":"2021-12-15T00:00:00Z","timestamp":1639526400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Combinatorial samplers are algorithmic schemes devised for the approximate- and exact-size generation of large random combinatorial structures, such as context-free words, various tree-like data structures, maps, tilings, RNA molecules. They can be adapted to combinatorial specifications with additional parameters, allowing for a more flexible control over the output profile of parametrised combinatorial patterns. One can control, for instance, the number of leaves, profile of node degrees in trees or the number of certain sub-patterns in generated strings. However, such a flexible control requires an additional and nontrivial tuning procedure. Using techniques of convex optimisation, we present an efficient tuning algorithm for multi-parametric combinatorial specifications. Our algorithm works in polynomial time in the system description length, the number of tuning parameters, the number of combinatorial classes in the specification, and the logarithm of the total target size. We demonstrate the effectiveness of our method on a series of practical examples, including rational, algebraic, and so-called P\u00f3lya specifications. We show how our method can be adapted to a broad range of less typical combinatorial constructions, including symmetric polynomials, labelled sets and cycles with cardinality lower bounds, simple increasing trees or substitutions. Finally, we discuss some practical aspects of our prototype tuner implementation and provide its benchmark results.<\/jats:p>","DOI":"10.1017\/s0963548321000547","type":"journal-article","created":{"date-parts":[[2021,12,15]],"date-time":"2021-12-15T09:51:28Z","timestamp":1639561888000},"page":"765-811","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers"],"prefix":"10.1017","volume":"31","author":[{"given":"Maciej","family":"Bendkowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olivier","family":"Bodini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey","family":"Dovgal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,12,15]]},"reference":[{"key":"S0963548321000547_ref14","doi-asserted-by":"crossref","unstructured":"[BGR15] Bodini, O. , Genitrini, A. and Rolin, N. (2015) Pointed versus singular Boltzmann samplers: a comparative analysis. Pure Math. Appl. 25(2) 115\u2013131.","DOI":"10.1515\/puma-2015-0012"},{"key":"S0963548321000547_ref10","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exx018"},{"key":"S0963548321000547_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-30528-9_7"},{"key":"S0963548321000547_ref49","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2018.1459620"},{"key":"S0963548321000547_ref67","doi-asserted-by":"publisher","DOI":"10.1007\/BF02509449"},{"key":"S0963548321000547_ref29","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<103::AID-RSA5>3.0.CO;2-Z"},{"key":"S0963548321000547_ref44","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90102-6"},{"key":"S0963548321000547_ref62","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<223::AID-RSA14>3.0.CO;2-O"},{"key":"S0963548321000547_ref15","doi-asserted-by":"crossref","unstructured":"[BLL98] Bergeron, F. , Labelle, G. and Leroux, P. (1998). Combinatorial Species and Tree-Like Structures. Vol. 67. Cambridge University Press.","DOI":"10.1017\/CBO9781107325913"},{"key":"S0963548321000547_ref64","doi-asserted-by":"crossref","unstructured":"[RNL08] Runciman, C. , Naylor, M. and Lindblad, F. (2008) Smallcheck and lazy smallcheck: Automatic exhaustive testing for small values. In Proceedings of the First ACM SIGPLAN Symposium on Haskell, Haskell \u201908. ACM, pp. 37\u201348. ISBN: 978-1-60558-064-7.","DOI":"10.1145\/1411286.1411292"},{"key":"S0963548321000547_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006315"},{"key":"S0963548321000547_ref19","unstructured":"[Bod10] Bodini, O. (2010) Autour de la g\u00e9n\u00e9ration al\u00e9atoire sous mod\u00e8le de Boltzmann [On random generation under Boltzmann models]. Habilitation. Universit\u00e9 Pierre et Marie Curie."},{"key":"S0963548321000547_ref56","doi-asserted-by":"crossref","unstructured":"[Pa+11] Pa\u0141ka, M. H. , Claessen, K. , Russo, A. and Hughes, J. (2011) Testing an optimising compiler by generating random lambda terms. In Proceedings of the 6th International Workshop on Automation of Software Test, AST 2011. ACM, pp. 91\u201397. ISBN: 978-1-4503-0592-1.","DOI":"10.1145\/1982595.1982615"},{"key":"S0963548321000547_ref60","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2012.05.007"},{"key":"S0963548321000547_ref46","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-016-9319-7"},{"key":"S0963548321000547_ref25","doi-asserted-by":"crossref","unstructured":"[Cla+00] Clarke, E. , Grumberg, O. , Jha, S. , Lu, Y. and Veith, H. (2000) Counterexample-guided abstraction refinement. Computer Aided Verification ( Emerson, E. A. and Sistla, A. P. , eds), Springer Berlin Heidelberg, pp. 154\u2013169. ISBN: 978-3-540-45047-4.","DOI":"10.1007\/10722167_15"},{"key":"S0963548321000547_ref39","unstructured":"[GG16] Gittenberger, B. and Go\u0141ebiewski, Z. (2016) On the number of lambda terms with prescribed size of their de Bruijn representation. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS, pp. 40:1\u201340:13."},{"key":"S0963548321000547_ref35","doi-asserted-by":"crossref","unstructured":"[Fus05] Fusy, \u00e9. (2005) Quadratic exact size and linear approximate size random generation of planargraphs. Discr. Math. & Theor. Comp. Sci., 125\u2013138.","DOI":"10.46298\/dmtcs.3362"},{"key":"S0963548321000547_ref52","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791"},{"key":"S0963548321000547_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.05.022"},{"key":"S0963548321000547_ref4","unstructured":"[Bar16] Barab\u00e1si, A.-L. (2016) Network Science. Cambridge University Press."},{"key":"S0963548321000547_ref28","doi-asserted-by":"publisher","DOI":"10.23919\/ECC.2013.6669541"},{"key":"S0963548321000547_ref45","unstructured":"[KY76] Knuth, D. and Yao, A. (1976) Algorithms and Complexity: New Directions and Recent Results. Academic Press. Chap. The complexity of nonuniform random number generation."},{"key":"S0963548321000547_ref41","doi-asserted-by":"crossref","unstructured":"[HHA97] Haugset, T. , Haugerud, H. and Andersen, J. O. (1997) Bose-Einstein condensation in anisotropic harmonic traps. Phys. Rev. A 55(4) 2922.","DOI":"10.1103\/PhysRevA.55.2922"},{"key":"S0963548321000547_ref65","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2016.7798400"},{"key":"S0963548321000547_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29221-2_9"},{"key":"S0963548321000547_ref7","doi-asserted-by":"crossref","unstructured":"[BBJ13] Bacher, A. , Bodini, O. and Jacquot, A. (2013) Exact-size sampling for Motzkin trees in linear time via Boltzmann samplers and holonomic specification. InProceedings of the Meeting on Analytic Algorithmics and Combinatorics, pp. 52\u201361.","DOI":"10.1137\/1.9781611973037.7"},{"key":"S0963548321000547_ref48","doi-asserted-by":"crossref","unstructured":"[LR08] Lucietti, J. and Rangamani, M. (2008) Asymptotic counting of BPS operators in superconformal field theories. J. Math. Phys. 49(8) 082301.","DOI":"10.1063\/1.2970775"},{"key":"S0963548321000547_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(83)90062-6"},{"key":"S0963548321000547_ref13","doi-asserted-by":"crossref","unstructured":"[BG12] Bernardi, O. and Gim\u00e9nez, O. (2012). A linear algorithm for the random sampling from regular languages. Algorithmica 62(1) 130\u2013145.","DOI":"10.1007\/s00453-010-9446-5"},{"key":"S0963548321000547_ref3","doi-asserted-by":"crossref","unstructured":"[Ban+12] Banderier, C. , Bodini, O. , Ponty, Y. and Bouzid, H.T. (2012) On the diversity ofpattern distributions in rational language. In Proceedings of the Ninth Workshop on Analytic Alg. and Combinatorics, pp. 107\u2013115.","DOI":"10.1137\/1.9781611973020.13"},{"key":"S0963548321000547_ref24","doi-asserted-by":"publisher","DOI":"10.1145\/351240.351266"},{"key":"S0963548321000547_ref37","doi-asserted-by":"crossref","unstructured":"[FZC94] Flajolet, P. , Zimmermann, P. and Van Cutsem, B. (1994) A calculus for the random generation of labelled combinatorial structures. Theor. Comput. Sci. 132(1) 1\u201335.","DOI":"10.1016\/0304-3975(94)90226-7"},{"key":"S0963548321000547_ref54","doi-asserted-by":"crossref","unstructured":"[ODo+16] O\u2019Donoghue, B. , Chu, E. , Parikh, N. and Boyd, S. (2016) Conic optimization via operator splitting and homogeneous self-dual embedding. J. Opt. Th. & App. 169(3) 1042\u20131068.","DOI":"10.1007\/s10957-016-0892-3"},{"key":"S0963548321000547_ref68","doi-asserted-by":"crossref","unstructured":"[WG01] Welsh, D. and Gale, A. (2001) The complexity of counting problems. Asp. Compl. de Gruyter Ser. Log. Appl., pp. 115\u2013154.","DOI":"10.1515\/9783110889178.115"},{"key":"S0963548321000547_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8405-1_10"},{"key":"S0963548321000547_ref42","doi-asserted-by":"crossref","unstructured":"[JVV86] Jerrum, M. R. , Valiant, L. G. and Vazirani, V. V. (1986) Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 43 169\u2013188.","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"S0963548321000547_ref36","doi-asserted-by":"publisher","DOI":"10.1016\/j.bbagen.2016.08.008"},{"key":"S0963548321000547_ref33","doi-asserted-by":"crossref","unstructured":"[FFP07] Flajolet, P. , Fusy, \u00e9. and Pivoteau, C. (2007) Boltzmann sampling of unlabelled structures. In Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, pp. 201\u2013211.","DOI":"10.1137\/1.9781611972979.5"},{"key":"S0963548321000547_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975062.9"},{"key":"S0963548321000547_ref17","doi-asserted-by":"publisher","DOI":"10.1137\/100790082"},{"key":"S0963548321000547_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s100510050691"},{"key":"S0963548321000547_ref5","doi-asserted-by":"crossref","unstructured":"[Bas+17] Bassino, F. , Bouvel, M. , Pierrot, A. , Pivoteau, C. and Rossin, D. (2017) An algorithm computing combinatorial specifications of permutation classes. Disc. Appl. Math. 224 16\u201344.","DOI":"10.1016\/j.dam.2017.02.013"},{"key":"S0963548321000547_ref34","doi-asserted-by":"crossref","unstructured":"[FS09] Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics. Cambridge University Press. ISBN: 978-0-521-89806-5.","DOI":"10.1017\/CBO9780511801655"},{"key":"S0963548321000547_ref1","doi-asserted-by":"crossref","unstructured":"[AA05] Albert, M. H. and Atkinson, M. D. (2005) Simple permutations and pattern restricted permutations. Disc. Math. 300(1\u20133) 1\u201315.","DOI":"10.1016\/j.disc.2005.06.016"},{"key":"S0963548321000547_ref58","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22102-1_22"},{"key":"S0963548321000547_ref59","doi-asserted-by":"publisher","DOI":"10.1038\/297197a0"},{"key":"S0963548321000547_ref69","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-04-01692-8"},{"key":"S0963548321000547_ref40","doi-asserted-by":"crossref","unstructured":"[Ham+19] Hammer, S. , Wang, W. , Will, S. and Ponty, Y. (2019) Fixed-parameter tractable sampling for RNA design with multiple target structures. BMC Bioinform. 20(1) 209.","DOI":"10.1186\/s12859-019-2784-7"},{"key":"S0963548321000547_ref50","unstructured":"[Nem04] Nemirovski, A. (2004) Interior Point Polynomial Time Methods in Convex Programming. Lecture Notes."},{"key":"S0963548321000547_ref63","first-page":"179","article-title":"Un proc\u00e9d\u00e9 it\u00e9ratif de d\u00e9nombrement d\u2019arbres binaires et son application \u00c0 leur g\u00e9n\u00e9ration al\u00e9atoire","volume":"19","author":"R\u00e9my","year":"1985","journal-title":"ITA"},{"key":"S0963548321000547_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/1385-7258(72)90034-0"},{"key":"S0963548321000547_ref18","doi-asserted-by":"crossref","unstructured":"[Bod+16] Bodini, O. , Dien, M. , Fontaine, X. , Genitrini, A. and Hwang, H.-K. (2016) Increasing diamonds. In Latin American Symposium on Theoretical Informatics, pp. 207\u2013219.","DOI":"10.1007\/978-3-662-49529-2_16"},{"key":"S0963548321000547_ref16","unstructured":"[BLR15] Bodini, O. , Lumbroso, J. and Rolin, N. (2015) Analytic samplers and the combinatorial rejection method. In Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, pp. 40\u201350."},{"key":"S0963548321000547_ref43","doi-asserted-by":"crossref","unstructured":"[Kar84] Karmarkar, N. A new polynomial-time algorithm for linear programming. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pp. 302\u2013311.","DOI":"10.1145\/800057.808695"},{"key":"S0963548321000547_ref8","doi-asserted-by":"crossref","unstructured":"[BBR14] Bouillard, A. , Bu\u0161ic, A. and Rovetta, C. (2014) Perfect sampling for closed queueing networks. Perform. Eval. 79 146\u2013159.","DOI":"10.1016\/j.peva.2014.07.010"},{"key":"S0963548321000547_ref55","doi-asserted-by":"publisher","DOI":"10.2307\/1969046"},{"key":"S0963548321000547_ref61","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00433-7"},{"key":"S0963548321000547_ref47","doi-asserted-by":"crossref","unstructured":"[LB14] Landau, D. P. and Binder, K. (2014). A Guide to Monte Carlo Simulations in Statistical Physics. Cambridge University Press.","DOI":"10.1017\/CBO9781139696463"},{"key":"S0963548321000547_ref20","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.2793"},{"key":"S0963548321000547_ref57","unstructured":"[Pa\u0142+11] Pa\u0142ka, M. H. (2012) Random structured test data generation for black-box testing. PhD thesis. Chalmers University of Technology."},{"key":"S0963548321000547_ref12","doi-asserted-by":"crossref","unstructured":"[BFR18] Bernstein, M. , Fahrbach, M. and Randall, D. (2018) Analyzing Boltzmann samplers for Bose\u2013Einstein condensates with Dirichlet generating functions. In 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pp. 107\u2013117. eprint: https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611975062.10.","DOI":"10.1137\/1.9781611975062.10"},{"key":"S0963548321000547_ref53","unstructured":"[NW78] Nijenhuis, A. and Wilf, H. S. (1978). Combinatorial Algorithms. 2nd ed. Academic Press."},{"key":"S0963548321000547_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990332"},{"key":"S0963548321000547_ref27","doi-asserted-by":"crossref","unstructured":"[CPW20] Chauve, C. , Ponty, Y. and Wallner, M. (2020) Counting and sampling gene family evolutionary histories in the duplication-loss and duplication-loss-transfer models. J. Math. Biol., 1\u201336.","DOI":"10.1007\/s00285-019-01465-x"},{"key":"S0963548321000547_ref32","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00323-5"},{"key":"S0963548321000547_ref51","first-page":"5","article-title":"Introductory lectures on convex programming volume I: Basic course","volume":"3","author":"Nesterov","year":"1998","journal-title":"Lecture Notes"},{"key":"S0963548321000547_ref66","doi-asserted-by":"publisher","DOI":"10.1007\/BF03025291"},{"key":"S0963548321000547_ref2","doi-asserted-by":"crossref","unstructured":"[Art+15] Arts, T. , Hughes, J. , Norell, U. and Svensson, H. (2015) Testing AUTOSAR software with QuickCheck. In 2015 IEEE Eighth International Conference on Software Testing, Verification and Validation Workshops (ICSTW), pp. 1\u20134.","DOI":"10.1109\/ICSTW.2015.7107466"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000547","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T13:16:05Z","timestamp":1726319765000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000547\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,15]]},"references-count":69,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["S0963548321000547"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000547","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2021,12,15]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}