use Benchmark qw(:all); use File::Path qw(mkpath); use application 'polytope'; # prints a progressbar # @param Int got : the amount of stuff you have already got # @param Int total : the total amount of stuff # @param String text : additional text behind the bar. sub progress_bar { my ( $got, $total, $text) = @_; my $width = 10; my $char = '='; local $| = 1; printf "|%-${width}s| $got/$total | %-80s \r", $char x (($width)*$got/$total). '>', $text; } # creates a certain knapsack polytope, where the coordinates from the normal vector # are the fibonacci sequence. Then it counts all lattice points and takes the time # @param String ch the prefered method # (possible options: projection, latte, _4ti2, libnormaliz, bbox) # @param Int d the dimension # @param Int b the right hand side of the inequality # @param Int start the first element of the fibonacci sequnce # @param Int start the second element of the fibonacci sequnce # @param Int nmz_dual if normaliz should run in dual mode sub time_knapsack($$$$$$) { my ($ch, $d, $b, $first, $second, $nmz_dual) = @_; my @ineq = ($b, -$first, -$second); for (my $i=2; $i < $d; ++$i) { my $third = $first + $second; $first = $second; $second = $third; push @ineq, -$third; } my $p = knapsack(\@ineq); # calculate FACETS and VERTICES before the timing starts prefer_now "ppl"; $p->FACETS; $p->VERTICES; my $t0; my $t1; # timing if (($ch eq "libnormaliz")){ $p->MONOID_GRADING; $t0=Benchmark->new; normaliz_compute($p, from_facets=>1, dual_algorithm=>$nmz_dual, degree_one_generators=>1); $t1=Benchmark->new; } else { my $target = ($ch eq "azove") ? "N_01POINTS" : "N_LATTICE_POINTS"; prefer_now $ch; my $s=$p->get_schedule("$target"); $t0=Benchmark->new; $s->apply($p); $t1=Benchmark->new; } my $t=timediff($t1,$t0); #print timestr($t)."\n"; if (($ch eq "projection") || ($ch eq "bbox") || ($ch eq "libnormaliz")){ return $t->[1]; } else { # measure child process only return $t->[3]; } } # counts lattice points from several fibonacci knapsack polytopes # @param Array ch the prefered method # (possible options: _4ti2, bbox, latte, libnormaliz, projection, bbox) # @param Int start_d the lower bound of the dimension # @param Int end_d the upper bound of the dimension # @param Int start_b the lower bound of the right hand side # @param Int end_b the upper bound of the right hand side # @param Int start the first element of the fibonacci sequnce # @param Int start the second element of the fibonacci sequnce # @option Int dimstep stepsize of the dimension # @option Int bstep stepsize of the right hand side # @option Int av number of experiments for one parameter set # @option Int time_limit maximum time (+10%) to skip following tests # @option String path output path # @option Hash only_once parameters that should run only once sub start_time_knapsack($$$$$$$;$) { my ($ch, $start_d, $end_d, $start_b, $end_b, $first, $second, $options) = @_; my $dimstep = $options->{"dimstep"}; # stepsize of the dimension my $bstep = $options->{"bstep"}; # stepsize of the right hand side my $av = $options->{"av"}; # number of experiements with the same parameterset my $path = $options->{"path"}; # output path my $only_once = $options->{"only_once"}; # which parameters should run only once my $time_limit = $options->{"time_limit"}; # time limit my $nmz_dual = $options->{"normaliz_dual"}; # if libnormaliz runs in dual mode # set defaults for options if (!defined($options->{"dimstep"})) { $dimstep=1; } if (!defined($options->{"bstep"})) { $bstep=10; } if (!defined($options->{"av"})) { $av=10; } if (!defined($options->{"path"})) { $path="."; } if (!defined($options->{"only_once"})) { $only_once = {}; } if (!defined($options->{"time_limit"})) { $time_limit = 3600; } if (!defined($options->{"normaliz_dual"})) { $nmz_dual = 0; } # create output path if (!-d $path){ mkpath $path or die "can't create ouput directory: $path"; } # convert $end_n to an array if (!(ref($end_b) eq "ARRAY")){ my @array=(); map { push @array, $end_b } ($start_d .. $end_d); $end_b = \@array; } # for pretty print for progress bar my $length_d = length $end_d; my $length_b = length $end_b->[0]; foreach my $chcode (@{$ch}) { my $skip = 0; my $file= "$path/knapsack_".$chcode."_$$.csv"; if(($chcode eq "libnormaliz") && ($nmz_dual == 1)){ $file= "$path/knapsack_".$chcode."_dual_$$.csv"; } # Open output file open OUTPUT_FILE, ">$file" or die "can't create outputfile $file: $!"; $|=1; OUTPUT_FILE->autoflush(1); print OUTPUT_FILE '"time(dimension x right side) where dimension starts from '.$start_d.' to '.$end_d.' (steps are '.$dimstep.') and the right hand side from '. $start_b.' to '. $end_b->[0].' (steps are '.$bstep.')"'. "\n"; print OUTPUT_FILE '"Matlab Commands: dim = '.$start_d.':'.$dimstep.':'.$end_d.' and b ='.$start_b.':'.$bstep.':'.$end_b->[0].' and mesh(points,b,import)"'."\n"; print "\n=== $chcode ===\n"; # first time without timing. Just to make sure no recompiling comes in the way #time_knapsack($chcode,$start_d,$start_b,$first,$second); for(my $d = $start_d; $d <= $end_d; $d+=$dimstep){ for(my $b = $start_b; $b <= $end_b->[$d-$start_d]; $b+=$bstep){ # For every set of parameters do $av experiments and take the average my $t = 0; my $date=localtime(time); my $localav = exists($only_once->{ "$d,$b" }) ? 1: $av; progress_bar(0,$localav,(sprintf "($d,$b): $date")); for(my $i=0; $i < $localav; ++$i){ my $time = time_knapsack($chcode,$d,$b,$first,$second, $nmz_dual); $t += $time; $date=localtime(time); progress_bar($i+1,$localav,(sprintf "($d,$b): %9.3f -- $date", $time)); if($time > 1.1*$time_limit){ $skip=1; $localav = $i+1; last; } } $t = sprintf "%.3f", $t/$localav; my $date=localtime(time); printf "(%${length_d}s,%${length_b}s): %9.3f -- %-80s\n", $d, $b, $t, $date; print OUTPUT_FILE $t.';'; last if($skip); } print OUTPUT_FILE "\n"; $skip = 0; } close OUTPUT_FILE; } } ## If you want to trigger the run commands automatically just remove the next line return; ### ## To use only one thread for normaliz set the following environment variable # export OMP_NUM_THREADS=1 ### ## to run latte in all primal mode use the polymake command # set_custom($latte_count_param="--irrational-all-primal --maxdet=25 --exponential"); ## and restart polymake $path = "/path/to/store/the/output/files"; ## experiments: just varying the dimension my $dpath = "$path/plots_dim/"; start_time_knapsack(["bbox", "projection","_4ti2"],4,20,60,60, 2,3, { path=>$dpath }); start_time_knapsack(["libnormaliz"],4,20,60,60, 2,3, { path=>$dpath }); start_time_knapsack(["libnormaliz"],4,20,60,60, 2,3, { path=>$dpath, normaliz_dual=>1 }); start_time_knapsack(["latte"],4,18,60,60, 2,3, { path=>$dpath }); # default #start_time_knapsack(["latte"],4,12,60,60, 2,3, { path=>$dpath }); # all_primal ## experiments: just varying the right hand side my $bpath = "$path/plots_rhs/"; start_time_knapsack(["bbox", "latte", "projection","libnormaliz"],5,5,40,200, 2,3, { path=>$bpath }); start_time_knapsack(["libnormaliz"],5,5,40,200, 2,3, { path=>$bpath }); start_time_knapsack(["libnormaliz"],5,5,40,200, 2,3, { path=>$bpath, normaliz_dual=>1 }); start_time_knapsack(["_4ti2"],5,5,40,90, 2,3, { path=>$bpath });