View More Publications

Uniform Random Sampling in Polyhedra

Benoit Meister, Philippe Clauss
Publication Source: 10th International Workshop on Polyhedral Compilation Techniques; IMPACT 2020, Bologna, Italy

We propose a method for generating uniform samples among a domain of integer points defined by a polyhedron in a multidimensional space. The method extends to domains defined by parametric polyhedra, in which a subset of the variables are symbolic. We motivate this work by a list of applications for the method in computer science. The proposed method relies on polyhedral ranking functions, as well as a recent inversion method for them, named trahrhe expressions.

Google Scholar    Article