Skip to content

volesti vs hitandrun

Tolis Chalkis edited this page Mar 20, 2020 · 5 revisions

In this topic we compare volesti with CRAN package hitandrun. We sample uniformly distributed points from convex polytopes and compare run-times. hitandrun supports only Random Directions Hit and Run (RDHR) and thus we use the same random walk from volesti. The following R script generates a random polytope for each dimension and samples 10000 points (walk length = 10) with both packages.

library(volesti)
library(hitandrun)
library(ggplot2)

N=1000
times_volesti = c()
times_hnr = c()
for (d in seq(from=10,to=100,by=10)) {
  
  P = gen_cube(d, 'H')
  tim = system.time({ sample_points(P, n=N, random_walk = list("walk" = "RDHR", "walk_length"=5)) })
  times_volesti = c(times_volesti, as.numeric(tim)[3])
  
  constr <- list(constr = P$A, dir=rep('<=', 2*d), rhs=P$b)
  tim = system.time({ hitandrun(constr, n.samples=N, thin=5) })
  times_hnr = c(times_hnr, as.numeric(tim)[3])
}

The following Table reports the run-times.

dimension volesti time hitandrun time
10 0.017 0.102
20 0.024 0.157
30 0.031 0.593
40 0.043 1.471
50 0.055 3.311
60 0.069 6.460
70 0.089 11.481
80 0.108 19.056
90 0.132 33.651
100 0.156 50.482

The following figure illustrates the asymptotic in the dimension difference in run-time between volesti and hitandrun.

ratio_times

Clone this wiki locally