Polyrun contains an implementation of Hit-and-Run algorithm (HAR) for uniform sampling from bounded convex polytopes defined by linear constraints, as well as three other sampling methods: BallWalk [2], SphereWalk, and GridWalk [3], exploiting a neighborhood of some interior point within the convex polytope. It is written in Java and described in this paper.
To add a dependency in your project's pom.xml use the following:
<dependency>
<groupId>com.github.kciomek</groupId>
<artifactId>polyrun</artifactId>
<version>1.1.0</version>
</dependency>
The software provides methods for sampling from convex polytopes defined by a system of linear constraints (inequalities and equalities):
Ax <= b
Cx = d
Consider sampling from the polytope defined by the following set of constraints:
x1, x2, x3 >= 0
x1 + x2 + x3 = 1
3 x1 + 0.5 x2 - 0.75 x3 >= 0
It defines a convex quadrangle in a three dimensional space:
First, this shape can be defined with the following code, where lhs and rhs denote, respectively, the left- and right-hand sides of the constraints, and dir specifies their types and directions:
final double[][] lhs = new double[][]{
{1, 0, 0},
{0, 1, 0},
{0, 0, 1},
{1, 1, 1},
{3, 0.5, -0.75}
};
final String[] dir = new String[]{">=", ">=", ">=", "=", ">="};
final double[] rhs = new double[]{0, 0, 0, 1, 0};
ConstraintsSystem constraints = new ConstraintsSystem(lhs, dir, rhs);Second, one needs to define an object of the PolytopeRunner class, which is responsible for sampling from the pre-defined polytope:
PolytopeRunner runner = new PolytopeRunner(constraints);It transforms the input constraints to a form which is appropriate for the sampling algorithms and removes the redundant constraints. There are two other constructors that allows for controlling the transformation settings.
Third, a starting point for the sampling algorithms needs to be set up. One may either provide a custom starting point with the setStartPoint method or use some built-in method for selecting such a point automatically in the following way:
runner.setAnyStartPoint(); // sets a point that is a result of slack maximizationFinally, PolytopeRunner may be used to generate a Markov chain of samples or to sample a neighborhood of the starting point. For example, the following code generates 1000 uniformly distributed samples using the Hit-and-Run method, taking only every 1.0 * n^3:
double[][] samples = runner.chain(new HitAndRun(),
new NCubedThinningFunction(1.0),
1000);
The results of such sampling procedure:
Even though the library provides some pre-defined thinning functions, one may define a custom one by implementing the ThinningFunction interface, and provide it as a second parameter to the chain method.
The procedure for sampling a neighbourhood of some interior point can be used analogously. It requires a starting point to be set up, and then calling the neighborhood method with a random walk sampling algorithm. For example, to generate 20 samples from a hyper-sphere of radius 0.15 around the [0.3, 0.1, 0.6] point, the following code should be executed:
runner.setStartPoint(new double[] {0.3, 0.1, 0.6});
double[][] neighborhood = runner.neighborhood(new ShereWalk(0.15, OutOfBoundsBehaviour.Crop), 20);If the generated samples would be outside the polytope, the algorithm crops them to the boundary.
Instead of allocating the memory for an array of complete results of the sampling algorithm, both chain and neighborhood methods can consume the samples already during the generation process. For this purpose, an interface SampleConsumer has to be implemented:
runner.chain(new HitAndRun(),
new LinearlyScalableThinningFunction(1.0),
1000,
new SampleConsumer() {
@Override
public void consume(double[] sample) {
// process 'sample'
}
});Both chain and neighborhood methods can be called with any RandomWalk depending on the application. All sampling algorithms accept custom random number generators in their constructors, what allows for performing the experiments whose results are reproducible.
This and other examples can be found here.
For a more detailed description of the library, refer to the API documentation.
The library allows customization. User can implement own ThinningFunction adjusting the skipping samples in the chain to the particular application. It is possible to provide a custom solver used by PolytopeRunner for slack maximization and removing redundant constraints. It can be done by implementing GLPSolver. Finally, the library provides interface RandomWalk. By extending it, the user can control random walk inside the polytope what results in custom sampling algorithm.
Besides the API, the software provides a Command Line Interface (CLI) for the Hit-and-Run algorithm. It allows for using the sampler without any coding.
To run polyrun as a command line tool Java Runtime Environment 1.6+ is required to be installed. The latest version of executable polyrun can be downloaded from here.
The input constraints are read from the standard input and the generated samples are written to the standard output. The input is required to contain one constraint per line in form:
<a_1> <a_2> ... <a_n> <type> <rhs>
where:
- <a_1>, <a_2>, ..., <a_n> are coefficients of the variables,
- <type> denotes a kind of constraint ('<=', '>=' or '='),
- <rhs> is a constant term,
- and all fields in the line are separated by whitespaces.
Each generated sample is written to standard output as a single line. The values are separated by tab, i.e.:
<sample1_1> <sample1_2> ... <sample1_n>
<sample2_1> <sample2_2> ... <sample2_n>
...
In order to use CLI, initially, an input file (e.g., input.txt) has to be prepared, e.g.:
1 0 0 >= 0
0 1 0 >= 0
0 0 1 >= 0
1 1 1 = 1
3 0.5 -0.75 >= 0
Then, running the following command in a terminal allows for generating 1000 uniformly distributed samples using Hit-and-Run:
java -jar polyrun-1.1.0-jar-with-dependencies.jar -n 1000 < input.txt
where parameter -n controls required number of samples. The other useful parameter is -s. It allows for providing a custom seed to random generator, what makes the experiments reproducible. For a detailed documentation of the implemented parameters, a help page can be viewed using the following command:
java -jar polyrun-1.1.0-jar-with-dependencies.jar -h
[1] R. L. Smith, Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions, Operations Research, 1984, 32:1296–1308. click to visit
[2] L. Lovász, M. Simonovits, Random walks in a convex body and an improved volume algorithm, Random Struct. Alg., 1993, 4:359-412. click to visit
[3] M. Dyer, A. Frieze, R. Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, J. ACM, 1991, 38:1-17. click to visit
[4] API documentation. click to visit
[5] Code examples. click to visit
If you find polyrun useful in your research, please consider citing:
@article{Ployrun2021,
title = {Polyrun: A Java library for sampling from the bounded convex polytopes},
author = {Krzysztof Ciomek and Miłosz Kadziński},
journal = {SoftwareX},
volume = {13},
pages = {100659},
year = {2021},
doi = {https://doi.org/10.1016/j.softx.2021.100659}
}
The MIT License (MIT)
Copyright (c) 2015-2021 Krzysztof Ciomek
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.