Computing convex hulls and counting integer points with polymake

Here we collect programs and data for the experiments reported on in the paper

• Benjamin Assarf, Ewgenij Gawrilow, Katrin Herr, Michael Joswig, Benjamin Lorenz, Andreas Paffenholz, Thomas Rehn: Computing convex hulls and counting integer points with polymake, Mathematical Programming Computation, March 2017, Volume 9, Issue 1, pp 1–38.

In integer and linear optimization the software workhorses are solvers for linear programs as well as generic frameworks for branch-and-bound or branch-and-cut schemes. While today it is common to solve linear programs with millions of rows and columns and, moreover, mixed integer linear programs with sometimes hundreds of thousands of rows and columns, big challenges remain. A main purpose of this note is to report on the state of the art of getting at the facets of the integer hull in a brute force kind of way. And we will do so by explaining how our software system polymake can help. First, we explore how various convex hull algorithms and implementations behave on various kinds of input. Our input is chosen according to typical scenarios which are motivated by computational tasks arising in optimization. Second, we look into enumerating lattice points in polytopes, which is actually the first step for this integer hull approach. We will sum up our experience in this area in several “rules of thumb”, all of which have to be taken with a grain of salt.

All experiments can be run with a clean polymake 2.15 beta 3 installation if the requirements for the corresponding bundled extensions are met (check the configure output):

• Convex hull computations up to symmetry need the group extension and thus the boost library.
• The ppl extension needs an installed version of the ppl library.
• libnormaliz comes with polymake but also needs boost. To use the multithreaded variant you need a compiler that supports OpenMP, i.e. gcc >=4.4. (The OpenMP support in clang is not complete yet!)
• 4ti2 needs to be installed and configured.
• LattE needs to be installed and configured.

• openSUSE 13.1 with with Linux kernel 3.11.10-25 and gcc 4.9.3, gmp 5.1.2 and perl 5.18.1
• polymake 2.15 beta 3
• cddlib 0.94h
• lrslib 6.0
• ppl 1.1
• libnormaliz 2.99.4
• 4ti2 1.6.6
• LattE 1.73
• azove 2.0
• porta 1.4.1-20090921

• CPU: AMD Phenom™ II X6 1090T
• bogomips: 6421.34
• MemTotal: 8191520 kB

If you want to use one of the following scripts in polymake load the script via

script("/path/to/the/script/file.script");

and run the commands suggested in the corresponding section below.

Some experiments are specifically set up to stress memory usage. Therefore we set a fixed limit to 4GB. If you feel like duplicating our experiments you should use the following shell command before starting polymake:

ulimit -v 4000000

Download the script and load it into polymake. Use the following commands to run the tests. You may download the output data here.

$path = "/path/to/store/the/output/files";
start_time_cut_polytope(["porta"],0,7, { path=>$path });
start_time_cut_polytope(["beneath_beyond"],0,4, { path=>$path, });
start_time_cut_polytope(["cdd"],0,9, { path=>$path });
start_time_cut_polytope(["lrs"],0,5, { path=>$path, only_once=>{"5"=>1 } });
start_time_cut_polytope(["ppl"],0,14, { path=>$path });
 
###
## If you want to use only one thread for normaliz set the following environment variable
## export OMP_NUM_THREADS=1
#start_time_cut_polytope(["libnormaliz"],0,14, { path=>$path, only_once=>{"14"=>1 } });
 
###
## If you want to use more than one thread for normaliz set the following environment variable
## export OMP_NUM_THREADS=6
#start_time_cut_polytope(["libnormaliz"],0,14, { path=>$path, only_once=>{"14"=>1 } });

Download the script and load it into polymake. Use the following commands to run the tests. You may download the output data here.

$path = "/path/to/store/the/output/files";
###
## To use only one thread for normaliz set the following environment variable
# export OMP_NUM_THREADS=1
 
start_time_knapsack(["libnormaliz", "porta", "beneath_beyond", "ppl"],4,6,40,100, 2,3, { path=>$path });
start_time_knapsack(["cdd"],4,6,40,[100,100,80],2,3, { path=>$path, only_once=>{"5,100"=>1} });
start_time_knapsack(["lrs"],4,6,40,[100,70,60],2,3, { path=>$path, only_once=>{"4,100"=>1,"5,70"=>1, "6,60"=>1} });
 
## different kinds of input sorting
## 1=random sorting, 2=vertices come first
start_time_knapsack(["beneath_beyond", "porta"],4,6,40,100, 2,3, { path=>$path, inputSort=>1 });
start_time_knapsack(["beneath_beyond", "porta"],4,6,40,100, 2,3, { path=>$path, inputSort=>2 });
 
start_time_knapsack(["lrs"],4,6,40,100,2,3, { path=>$path, inputSort=>1 });
start_time_knapsack(["lrs"],4,6,40,100,2,3, { path=>$path, inputSort=>2 });
 
start_time_knapsack(["cdd"],4,6,40,100,2,3, { path=>$path, inputSort=>1 });
start_time_knapsack(["cdd"],4,6,40,100,2,3, { path=>$path, inputSort=>2 });

Download the script and load it into polymake. Use the following commands to run the tests. You may download the output data here.

# set environment: export OMP_NUM_THREADS=1
 
$path = "/path/to/store/the/output/files";
# no porta because coordinates are too ugly (porta does not use gmp)
start_time_voronoi(["beneath_beyond"],3,7,500,[3000,3000,3000,3000,1000], { path=>$path, only_once=>{"7,1000"=>1 } });
start_time_voronoi(["cdd"],3,6,500,[3000,3000,1500,500], { path=>$path, "5,1500"=>1  });
start_time_voronoi(["lrs"],3,7,500,[3000,3000,3000,3000,1000], { path=>$path, only_once=>{"6,3000"=>1 } });
start_time_voronoi(["libnormaliz"],3,7,500,[3000,3000,3000,1500,500], { path=>$path });
start_time_voronoi(["ppl"],3,6,500,[3000,3000,2500,1000], { path=>$path, only_once=>{"5,2500"=>1, "6,1000"=>1 } });
 
## Running one example many times (1000) to check standard deviation
#stats_voronoi(["beneath_beyond","cdd","lrs","ppl","libnormaliz"],5,500,1000, { path=>$path } );

Download the script and load it into polymake. Use the following commands to run the tests. You may download the output data here.

$n_runs = 10;
$choose_induced_syms = 1; # uses induced symmetries of graph instead of linear symmetries of cut polytope (set to 0 for linear symmetries!)
 
$path = "/path/to/store/the/output/files";
foreach my $n_nodes (9,10) {
    time_path($n_nodes,$n_runs,$path);
    time_cycle($n_nodes,$n_runs,$path);
    time_path_sym($n_nodes,$n_runs,$choose_induced_syms,$path);
    time_cycle_sym($n_nodes,$n_runs,$choose_induced_syms,$path);
}
 
 time_Kn(6,$n_runs,$path);
 time_Kn_sym(6,$n_runs,$choose_induced_syms,$path);
 time_Kn(7,1,$path);
 time_Kn_sym(7,$n_runs,$choose_induced_syms,$path);

Download the script and load it into polymake. Use the following commands to run the tests. You may download the output data here.

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

Download the script and load it into polymake. Use the following commands to run the tests. You may download the output data here.

###
## 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";
start_time_rand_box(["libnormaliz"],4,9,20,70,{ path=>$path });
start_time_rand_box(["projection"],4,9,20,70,{ path=>$path });
start_time_rand_box(["bbox"],4,9,20,[70,70,70,70,70,40],{ path=>$path });
start_time_rand_box(["latte"],4,7,20,70,{ path=>$path });
# 4ti2 and nmz dual disabled due to high variance, see below
#start_time_rand_box(["_4ti2"],4,7,20,70,{ path=>$path });
#start_time_rand_box(["libnormaliz"],4,5,20,[70,30],{ path=>$path, normaliz_dual=>1 });
 
 
## Running one example many times (100) to check standard deviation
stats_rand_box(["libnormaliz","projection","bbox"],6,50,100, { path=>$path } );
stats_rand_box(["projection","bbox"],6,50,100, { path=>$path } );
stats_rand_box(["latte"],4,20,100, { path=>$path } );
 
## These tests produce a high variance
#stats_rand_box(["libnormaliz"],4,20,100, { path=>$path, normaliz_dual=>1 } );
## Setting a ulimit on time aborts the extreme cases after one hour
# ulimit -t 3600
#stats_rand_box(["_4ti2"],4,20,100, { path=>$path } );

Download the script and load it into polymake. Use the following commands to run the tests. You may download the output data here.

###
## To use only one thread for normaliz set the following environment variable
# export OMP_NUM_THREADS=1
$path = "/path/to/store/the/output/files";
 
start_time_matching_polytope(["azove"],4,19, { path=>$path });
start_time_matching_polytope(["_4ti2"],4,9, { path=>$path });
start_time_matching_polytope(["bbox"],4,7, { path=>$path });
start_time_matching_polytope(["projection"],4,9, { path=>$path });
start_time_matching_polytope(["libnormaliz"],4,7, { path=>$path });
start_time_matching_polytope(["libnormaliz"],4,10, { path=>$path, normaliz_dual=>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
start_time_matching_polytope(["latte"],4,7, { path=>$path }); # default
#start_time_matching_polytope(["latte"],4,5, { path=>$path }); # all primal