A Practical Algorithm for Volume Estimation based on Billiard Trajectories and Simulated Annealing

Apostolos Chalkis, Ioannis Z. Emiris, Vissarion FisikopoulosACM J. Exp. Algorithmics 2023 · DOI · OpenReview

Abstract

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.
BibTeX
@article{chalkis2023practical,
  author = {Apostolos Chalkis and Ioannis Z. Emiris and Vissarion Fisikopoulos},
  title = {{A Practical Algorithm for Volume Estimation based on Billiard Trajectories and Simulated Annealing}},
  journal = {ACM J. Exp. Algorithmics},
  year = {2023},
  doi = {10.1145/3584182},
}

Loading related content...

Figure