{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T07:28:35Z","timestamp":1757575715919,"version":"3.41.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T00:00:00Z","timestamp":1683763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>We tackle the problem of efficiently approximating the volume of convex polytopes, when these are given in three different representations: H-polytopes, which have been studied extensively, V-polytopes, and zonotopes (Z-polytopes). We design a novel practical Multiphase Monte Carlo algorithm that leverages random walks based on billiard trajectories, as well as a new empirical convergence test and a simulated annealing schedule of adaptive convex bodies. After tuning several parameters of our proposed method, we present a detailed experimental evaluation of our tuned algorithm using a rich dataset containing Birkhoff polytopes and polytopes from structural biology. Our open-source implementation tackles problems that have been intractable so far, offering the first software to scale up in thousands of dimensions for H-polytopes and in the hundreds for V- and Z-polytopes on moderate hardware. Last, we illustrate our software in evaluating Z-polytope approximations.<\/jats:p>","DOI":"10.1145\/3584182","type":"journal-article","created":{"date-parts":[[2023,3,3]],"date-time":"2023-03-03T11:06:23Z","timestamp":1677841583000},"page":"1-34","source":"Crossref","is-referenced-by-count":2,"title":["A Practical Algorithm\u00a0for Volume Estimation based on Billiard Trajectories and Simulated Annealing"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4628-1907","authenticated-orcid":false,"given":"Apostolos","family":"Chalkis","sequence":"first","affiliation":[{"name":"Department of Informatics &amp; Telecommunications National &amp; Kapodistrian University of Athens, Greece, Athena Research Center, Greece and GeomScale"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2339-5303","authenticated-orcid":false,"given":"Ioannis Z.","family":"Emiris","sequence":"additional","affiliation":[{"name":"Athena Research Center, Maroussi, Greece and Department of Informatics &amp; Telecommunications National &amp; Kapodistrian University of Athens, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0780-666X","authenticated-orcid":false,"given":"Vissarion","family":"Fisikopoulos","sequence":"additional","affiliation":[{"name":"Department of Informatics &amp; Telecommunications National &amp; Kapodistrian University of Athens, Greece and GeomScale"}]}],"member":"320","published-online":{"date-parts":[[2023,5,11]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-09-00650-X"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2014.2312453"},{"key":"e_1_3_3_4_2","unstructured":"Shiri Artstein-Avidan Haim Kaplan and Micha Sharir. 2020. On Radial Isotropic Position: Theory and Algorithms. (2020). arxiv:cs.CG\/2005.04918."},{"key":"e_1_3_3_5_2","volume-title":"lp_solve 5.5, Open Source (Mixed-Integer) Linear Programming System","author":"Berkelaar M.","year":"2004","unstructured":"M. Berkelaar, K. Eikland, and P. Notebaert. 2004. lp_solve 5.5, Open Source (Mixed-Integer) Linear Programming System. http:\/\/lpsolve.sourceforge.net\/5.5\/."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008733"},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"Boyd Stephen","year":"2004","unstructured":"Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press, New York, NY, USA."},{"key":"e_1_3_3_8_2","first-page":"244","volume-title":"39th Symp. Foundations of Computer Science (FOCS)","author":"Brieden A.","year":"1998","unstructured":"A. Brieden, P. Gritzmann, R. Kannan, V. Klee, L. Lov\u00e1sz, and M. Simonovits. 1998. Approximation of diameters: Randomization doesn\u2019t help. In 39th Symp. Foundations of Computer Science (FOCS). 244\u2013251."},{"key":"e_1_3_3_9_2","volume-title":"7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019","author":"Brock Andrew","year":"2019","unstructured":"Andrew Brock, Jeff Donahue, and Karen Simonyan. 2019. Large scale GAN training for high fidelity natural image synthesis. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net."},{"key":"e_1_3_3_10_2","unstructured":"B. B\u00fceler and A. Enge. 2000. VINCI. (2000). http:\/\/www.math.u-bordeaux1.fr\/aenge\/index.php?category=software&page=vinci."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2018.19"},{"key":"e_1_3_3_12_2","unstructured":"E. Rodney Canfield and Brendan D. McKay. 2007. The asymptotic volume of the Birkhoff polytope. (2007). arxiv:math.CO\/0705.2422."},{"key":"e_1_3_3_13_2","first-page":"890","article-title":"Goffin\u2019s algorithm for zonotopes","volume":"48","author":"Cern\u00fd Michal","year":"2012","unstructured":"Michal Cern\u00fd. 2012. Goffin\u2019s algorithm for zonotopes. Kybernetika 48 (2012), 890\u2013906.","journal-title":"Kybernetika"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.32614\/RJ-2021-077"},{"key":"e_1_3_3_15_2","volume-title":"International Symposium on Computational Geometry, SoCG (LIPIcs)","author":"Chalkis Apostolos","year":"2021","unstructured":"Apostolos Chalkis, Vissarion Fisikopoulos, Elias Tsigaridas, and Haris Zafeiropoulos. 2021. Geometric algorithms for sampling the flux space of metabolic networks. In International Symposium on Computational Geometry, SoCG (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. https:\/\/arxiv.org\/pdf\/2012.05503. to appear."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-021-00558-4"},{"key":"e_1_3_3_17_2","first-page":"539","volume-title":"Proc. ACM STOC","author":"Cousins B.","year":"2015","unstructured":"B. Cousins and S. Vempala. 2015. Bypassing KLS: Gaussian cooling and an \\({O}^*(n^3)\\) volume algorithm. In Proc. ACM STOC. 539\u2013548."},{"key":"e_1_3_3_18_2","doi-asserted-by":"crossref","DOI":"10.1007\/s12532-015-0097-z","article-title":"A practical volume algorithm","volume":"8","author":"Cousins B.","year":"2016","unstructured":"B. Cousins and S. Vempala. 2016. A practical volume algorithm. Mathematical Programming Computation 8 (2016). Issue 2.","journal-title":"Mathematical Programming Computation"},{"key":"e_1_3_3_19_2","volume-title":"Mathematical Methods of Statistics","author":"Cramer H.","year":"1946","unstructured":"H. Cramer. 1946. Mathematical Methods of Statistics. Princeton University Press."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/080742506"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02243018"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217060"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.102782.102783"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187701"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3194656"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","DOI":"10.1201\/9781482296426","volume-title":"Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference","author":"Gamerman Dani","year":"2006","unstructured":"Dani Gamerman and Hedibert F. Lopes. 2006. Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference. CRC Press."},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/978-3-319-19647-3_6","volume-title":"Frontiers in Algorithmics","author":"Ge C.","year":"2015","unstructured":"C. Ge and F. Ma. 2015. A fast and practical method to estimate volumes of convex polytopes. In Frontiers in Algorithmics, J. Wang and C. Yap (Eds.). Springer, 52\u201365."},{"key":"e_1_3_3_28_2","unstructured":"Charles J. Geyer. 1991. Markov Chain Monte Carlo maximum likelihood. Interface Foundation of North America. http:\/\/conservancy.umn.edu\/handle\/11299\/58440. Accepted: 2010-02-24T20:38:06Z."},{"key":"e_1_3_3_29_2","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.laa.2010.01.031","article-title":"Determinants and the volumes of parallelotopes and zonotopes","volume":"413","author":"Gover E.","year":"2010","unstructured":"E. Gover and N. Krikorian. 2010. Determinants and the volumes of parallelotopes and zonotopes. Linear Algebra Appl. 413 (2010), 28\u201340.","journal-title":"Linear Algebra Appl."},{"key":"e_1_3_3_30_2","volume-title":"Eigen v3","author":"Guennebaud Ga\u00ebl","year":"2010","unstructured":"Ga\u00ebl Guennebaud, Beno\u00eet Jacob, et\u00a0al. 2010. Eigen v3. http:\/\/eigen.tuxfamily.org."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx052"},{"key":"e_1_3_3_32_2","first-page":"733","volume-title":"2017 IEEE 56th Annual Conference on Decision and Control (CDC)","author":"He Runxin","year":"2017","unstructured":"Runxin He and Humberto Gonzalez. 2017. Numerical synthesis of Pontryagin optimal control minimizers using sampling-based methods. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC). IEEE, 733\u2013738."},{"key":"e_1_3_3_33_2","doi-asserted-by":"crossref","first-page":"2865","DOI":"10.1109\/ICRA.2012.6225158","volume-title":"2012 IEEE International Conference on Robotics and Automation","author":"Huynh Vu Anh","year":"2012","unstructured":"Vu Anh Huynh, Sertac Karaman, and Emilio Frazzoli. 2012. An incremental sampling-based algorithm for stochastic optimal control. In 2012 IEEE International Conference on Robotics and Automation. IEEE, 2865\u20132872."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/0909028"},{"key":"e_1_3_3_35_2","unstructured":"H. Jia A. Laddha Y. T. Lee and S. S. Vempala. 2020. Reducing Isotropy and Volume to KLS: An  \\(O(n^3\\psi ^2)\\)  Volume Algorithm. (2020). arxiv:cs.DS\/2008.02146"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-0439-4_9"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2015.0202"},{"issue":"2","key":"e_1_3_3_38_2","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1287\/moor.1060.0194","article-title":"Simulated annealing for convex optimization","volume":"31","author":"Kalai Adam Tauman","year":"2006","unstructured":"Adam Tauman Kalai and Santosh Vempala. 2006. Simulated annealing for convex optimization. Mathematics of Operations Research 31, 2 (2006), 253\u2013266. https:\/\/www.jstor.org\/stable\/25151723. Publisher: INFORMS.","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"e_1_3_3_39_2","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1287\/opre.46.1.84","article-title":"Direction choice for accelerated convergence in Hit-and-Run sampling","volume":"46","author":"Kaufman D. E.","year":"1998","unstructured":"D. E. Kaufman and R. L. Smith. 1998. Direction choice for accelerated convergence in Hit-and-Run sampling. Operations Research 46, 1 (1998), 84\u201395. https:\/\/www.jstor.org\/stable\/223065.","journal-title":"Operations Research"},{"key":"e_1_3_3_40_2","first-page":"46:1\u201346:15","volume-title":"33rd Intern. Symp. Computational Geometry (SoCG 2017)","author":"Kerber M.","year":"2017","unstructured":"M. Kerber, R. Tichy, and M. F. Weitzer. 2017. Constrained triangulations, volumes of polytopes, and unit equations. In 33rd Intern. Symp. Computational Geometry (SoCG 2017). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany, 46:1\u201346:15."},{"key":"e_1_3_3_41_2","article-title":"Sampling with Riemannian Hamiltonian Monte Carlo in a constrained space","volume":"2202","author":"Kook Yunbum","year":"2022","unstructured":"Yunbum Kook, Yin Tat Lee, Ruoqi Shen, and Santosh S. Vempala. 2022. Sampling with Riemannian Hamiltonian Monte Carlo in a constrained space. CoRR abs\/2202.01908 (2022). arXiv:2202.01908. https:\/\/arxiv.org\/abs\/2202.01908.","journal-title":"CoRR"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2017.8264508"},{"key":"e_1_3_3_43_2","article-title":"A software package for sequential quadratic programming","author":"Kraft D.","year":"1988","unstructured":"D. Kraft. 1988. A software package for sequential quadratic programming. Technical Report, DFVLR-FB 88-28, Institut f\u00fcr Dynamik der Flugsysteme (1988).","journal-title":"Technical Report, DFVLR-FB 88-28, Institut f\u00fcr Dynamik der Flugsysteme"},{"key":"e_1_3_3_44_2","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF02684450","article-title":"Rigorously computed orbits of dynamical systems without the wrapping effect","volume":"61","author":"K\u00fchn W.","year":"1998","unstructured":"W. K\u00fchn. 1998. Rigorously computed orbits of dynamical systems without the wrapping effect. Computing 61 (1998), 47\u201367.","journal-title":"Computing"},{"key":"e_1_3_3_45_2","unstructured":"Aditi Laddha and Santosh Vempala. 2020. Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast. (2020). arxiv:cs.DS\/2009.11338."},{"key":"e_1_3_3_46_2","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/3188745.3188774","volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018)","author":"Lee Y. T.","year":"2018","unstructured":"Y. T. Lee and S. S. Vempala. 2018. Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018). Association for Computing Machinery, New York, NY, USA, 1115\u20131121. 10.1145\/3188745.3188774"},{"key":"e_1_3_3_47_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X","article-title":"Random walks and an  \\({O}^*(n^5)\\)  volume algorithm for convex bodies","volume":"11","author":"Lov\u00e1sz L.","year":"1997","unstructured":"L. Lov\u00e1sz, R. Kannan, and M. Simonovits. 1997. Random walks and an \\({O}^*(n^5)\\) volume algorithm for convex bodies. Random Structures and Algorithms 11 (1997), 1\u201350.","journal-title":"Random Structures and Algorithms"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970544727X"},{"key":"e_1_3_3_49_2","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/j.jcss.2005.08.004","article-title":"Simulated annealing in convex bodies and an O \\(^*(n^4)\\)  volume algorithms","volume":"72","author":"Lov\u00e1sz L.","year":"2006","unstructured":"L. Lov\u00e1sz and S. Vempala. 2006. Simulated annealing in convex bodies and an O \\(^*(n^4)\\) volume algorithms. J. Computer & System Sciences 72 (2006), 392\u2013417.","journal-title":"J. Computer & System Sciences"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00082"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dsp.2016.07.013"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-72634-2_6"},{"key":"e_1_3_3_53_2","volume-title":"Ball Centers of Special Polytopes","author":"Murty K. G.","year":"2009","unstructured":"K. G. Murty. 2009. Ball Centers of Special Polytopes. Technical Report. Department of Industrial & Operations Engineering, University of Michigan."},{"key":"e_1_3_3_54_2","unstructured":"Hariharan Narayanan and Piyush Srivastava. 2020. On the mixing time of coordinate Hit-and-Run. (2020). arxiv:cs.DS\/2009.14004."},{"issue":"11","key":"e_1_3_3_55_2","first-page":"2","article-title":"MCMC using Hamiltonian dynamics","volume":"2","author":"Neal Radford M.","year":"2011","unstructured":"Radford M. Neal et\u00a0al. 2011. MCMC using Hamiltonian dynamics. Handbook of Markov Chain Monte Carlo 2, 11 (2011), 2.","journal-title":"Handbook of Markov Chain Monte Carlo"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139020"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.3182\/20140824-6-ZA-1003.02312"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.3390\/metabo10020066"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1074\/jbc.R800048200"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1968.1098903"},{"key":"e_1_3_3_61_2","volume-title":"AAAI Conference on Artificial Intelligence","author":"Talvitie T.","year":"2018","unstructured":"T. Talvitie, K. Kangas, T. Niinim\u00e4ki, and M. Koivisto. 2018. Counting linear extensions in practice: MCMC versus exponential Monte Carlo. In AAAI Conference on Artificial Intelligence. https:\/\/aaai.org\/ocs\/index.php\/AAAI\/AAAI18\/paper\/view\/16957."},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.02.013"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.epsr.2020.106614"},{"issue":"4","key":"e_1_3_3_64_2","doi-asserted-by":"crossref","first-page":"809","DOI":"10.1093\/biomet\/90.4.809","article-title":"Efficient estimation of covariance selection models","volume":"90","author":"Wong Frederick","year":"2003","unstructured":"Frederick Wong, Christopher K. Carter, and Robert Kohn. 2003. Efficient estimation of covariance selection models. Biometrika 90, 4 (2003), 809\u2013830. http:\/\/www.jstor.org\/stable\/30042090.","journal-title":"Biometrika"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584182","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584182","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:05Z","timestamp":1750183685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584182"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,11]]},"references-count":63,"alternative-id":["10.1145\/3584182"],"URL":"https:\/\/doi.org\/10.1145\/3584182","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2023,5,11]]}}}