Skip to content

Shake and Bake ‐ Sampling from the boundary of convex polytopes

Jump to bottom
Vissarion Fisikopoulos edited this page Mar 18, 2025 · 5 revisions

Overview

This project aims to implement the Shake and Bake algorithm for sampling uniformly from the boundary of a convex polytope. Sampling from the boundary of polytopes has important applications in computational geometry, optimization, and metabolic network analysis. The implementation will enhance the existing C++ library volesti, a state-of-the-art tool for volume estimation and convex body sampling. The contributor will integrate this functionality into Rvolesti (the R interface for volesti) and dingo (that relies on volesti for sampling).

Technical Details

  • Implement the Shake and Bake algorithm in C++ within volesti. This algorithm is based on a Markov Chain Monte Carlo (MCMC) approach that generates points uniformly distributed on the boundary of a convex polytope.
  • Ensure efficient handling of high-dimensional polytopes using advanced numerical techniques and optimizations.
  • Design and implement robust unit tests and benchmarks to evaluate correctness and efficiency.
  • Extend Rvolesti by adding an R interface for the new boundary sampling functionality, following existing volesti conventions.
  • Integrate the new feature into dingo, enabling metabolic network analysis workflows to utilize boundary sampling.
  • Provide comprehensive documentation, including usage examples and integration guides for both Rvolesti and dingo.

Difficulty: Hard

Size

Large (350 hours)

References

[1] Shake-And-Bake Algorithms for Generating Uniform Points on the Boundary of Bounded Polyhedra, C. G. E. Boender, R. J. Caron, J. F. McDonald, A. H. G. Rinnooy Kan, H. E. Romeijn, R. L. Smith, J. Telgen and A. C. F. Vorst, 1991.
[2] "Shake and Bake" sampler, https://rdrr.io/cran/hitandrun/man/shakeandbake.html.

Skills

  • Required: C++, probability theory, linear algebra
  • Preferred: Experience with mathematical software is a plus

Mentors

  • Vissarion Fisikopoulos <vissarion.fisikopoulos at gmail.com> is an international expert in mathematical software, computational geometry, and optimization, and has previous GSOC mentoring experience with Boost C++ libraries (2016-2020) and the R-project (2017-2019).

  • Elias Tsigaridas <elias.tsigaridas at inria.fr> is an expert in computational nonlinear algebra and geometry with experience in mathematical software. He has contributed to the implementation, in C and C++, of several solving algorithms for various open source computer algebra libraries and has previous GSOC mentoring experience with the R-project (2019) and Geomscale (2020).

Tests

  • Implement a boundary sampling algorithm for an n-dimensional cube. Test the implementation for n = 10, 50, 100. What is the expected distance from the center of the cube? Compute the expected distance using the generated samples and comment on the results.
  • Improve the above implementation to exploit sparsity. Provide an alternative implementation the use volesti functions. Compare the two methods.
Clone this wiki locally