volume {volesti}

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 = FALSE)

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 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.

• seed A fixed seed for the number generator.

rounding

A boolean parameter for rounding. The default value is FALSE.

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

# 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))