volesti (version 1.1.2-9)

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

Value

The approximation of the volume of a convex polytope.

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.

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