volesti (version 1.1.0)

volume: The main function for volume approximation of a convex Polytope (H-polytope, V-polytope, zonotope or intersection of two V-polytopes)

Description

For the volume approximation can be used three algorithms. Either CoolingBodies (CB) or SequenceOfBalls (SOB) or CoolingGaussian (CG). An H-polytope with \(m\) facets is described by a \(m\times d\) matrix \(A\) and a \(m\)-dimensional vector \(b\), s.t.: \(P=\{x\ |\ Ax\leq b\} \). A V-polytope is defined as the convex hull of \(m\) \(d\)-dimensional points which correspond to the vertices of P. A zonotope is desrcibed by the Minkowski sum of \(m\) \(d\)-dimensional segments.

Usage

volume(P, settings = NULL, rounding = NULL, seed = NULL)

Arguments

P

A convex polytope. It is an object from class a) Hpolytope or b) Vpolytope or c) Zonotope or d) VpolytopeIntersection.

settings

Optional. A list that declares which algorithm, random walk and values of parameters to use, as follows:

• algorithm A string to set the algorithm to use: a) 'CB' for CB algorithm, b) 'SoB' for SOB algorithm or b) 'CG' for CG algorithm. The defalut algorithm for H-polytopes is 'CB' when \(d\leq 200\) and 'CG' when \(d>200\). For the other representations the default algorithm is 'CB'.

• error A numeric value to set the upper bound for the approximation error. The default value is \(1\) for SOB algorithm and \(0.1\) otherwise.

• random_walk A string that declares the random walk method: a) 'CDHR' for Coordinate Directions Hit-and-Run, b) 'RDHR' for Random Directions Hit-and-Run, c) 'BaW' for Ball Walk, or 'BiW' for Billiard walk. For CB and SOB algorithms the default walk is 'CDHR' for H-polytopes and 'BiW' for the other representations. For CG algorithm the default walk is 'CDHR' for H-polytopes and 'RDHR' for the other representations.

• walk_length An integer to set the number of the steps for the random walk. The default value is \(\lfloor 10 + d/10\rfloor\) for 'SOB' and \(1\) otherwise.

• win_len The length of the sliding window for CB or CG algorithm. The default value is \(400+3d^2\) for CB or \(500+4d^2\) for CG.

• hpoly A boolean parameter to use H-polytopes in MMC of CB algorithm when the input polytope is a zonotope. The default value is TRUE when the order of the zonotope is \(<5\), otherwise it is FALSE.

rounding

Optional. A boolean parameter for rounding. The default value is TRUE for V-polytopes and FALSE otherwise.

seed

Optional. A fixed seed for the number generator.

Value

The approximation of the volume of a convex polytope.

References

I.Z.Emiris and V. Fisikopoulos, “Practical polytope volume approximation,” ACM Trans. Math. Soft., 2018.,

A. Chalkis and I.Z.Emiris and V. Fisikopoulos, “Practical Volume Estimation by a New Annealing Schedule for Cooling Convex Bodies,” CoRR, abs/1905.05494, 2019.,

B. Cousins and S. Vempala, “A practical volume algorithm,” Springer-Verlag Berlin Heidelberg and The Mathematical Programming Society, 2015.

Examples

# NOT RUN {
# calling SOB algorithm for a H-polytope (3d unit simplex)
HP = gen_cube(3,'H')
vol = volume(HP)

# calling CG algorithm for a V-polytope (2d simplex)
VP = gen_simplex(2,'V')
vol = volume(VP, settings = list("algorithm" = "CG"))

# calling CG algorithm for a 2-dimensional zonotope defined as the Minkowski sum of 4 segments
Z = gen_rand_zonotope(2, 4)
vol = volume(Z, settings = list("random_walk" = "RDHR", "walk_length" = 2))

# }