Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revisionLast revisionBoth sides next revision | ||
researchdata:polymakeilp [2015/02/03 09:33] – [Caveat] assarf | user_guide:tutorials:polymakeilp [2019/01/25 13:56] – ↷ Page moved from researchdata:polymakeilp to user_guide:tutorials:polymakeilp oroehrig | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== | + | ====== |
+ | |||
Here we collect programs and data for the experiments reported on in the paper | 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: polymake in Linear and Integer Programming, | + | * Benjamin Assarf, Ewgenij Gawrilow, Katrin Herr, Michael Joswig, Benjamin Lorenz, Andreas Paffenholz, Thomas Rehn: [[https://link.springer.com/article/10.1007/ |
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", | 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", | ||
Line 8: | Line 10: | ||
===== Experimental setup ===== | ===== Experimental setup ===== | ||
- | All experiments can be run with a clean polymake 2.13 installation if the requirements for the corresponding bundled extensions are met (check the configure output): | + | 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 [[http:// | * Convex hull computations up to symmetry need the group extension and thus the [[http:// | ||
* The ppl extension needs an installed version of the [[http:// | * The ppl extension needs an installed version of the [[http:// | ||
Line 17: | Line 19: | ||
=== Software versions used for the experiments in the paper === | === Software versions used for the experiments in the paper === | ||
- | * openSUSE 13.1 with gcc 4.8.1, gmp 5.1.2 and perl 5.18.1 | + | * 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.13 | + | * polymake 2.15 beta 3 |
- | * cddlib 0.94f | + | * cddlib 0.94h |
- | * lrslib | + | * lrslib |
* ppl 1.1 | * ppl 1.1 | ||
- | * libnormaliz 2.10.1 | + | * libnormaliz 2.99.4 |
- | * 4ti2 1.6.2 | + | * 4ti2 1.6.6 |
- | * LattE 1.6 | + | * LattE 1.73 |
+ | * azove 2.0 | ||
+ | * porta 1.4.1-20090921 | ||
=== Hardware === | === Hardware === | ||
Line 51: | Line 55: | ||
<code perl> | <code perl> | ||
$path = "/ | $path = "/ | ||
+ | start_time_cut_polytope([" | ||
start_time_cut_polytope([" | start_time_cut_polytope([" | ||
start_time_cut_polytope([" | start_time_cut_polytope([" | ||
start_time_cut_polytope([" | start_time_cut_polytope([" | ||
- | start_time_cut_polytope([" | + | start_time_cut_polytope([" |
### | ### | ||
## If you want to use only one thread for normaliz set the following environment variable | ## If you want to use only one thread for normaliz set the following environment variable | ||
## export OMP_NUM_THREADS=1 | ## export OMP_NUM_THREADS=1 | ||
- | start_time_cut_polytope([" | + | #start_time_cut_polytope([" |
### | ### | ||
## If you want to use more than one thread for normaliz set the following environment variable | ## If you want to use more than one thread for normaliz set the following environment variable | ||
## export OMP_NUM_THREADS=6 | ## export OMP_NUM_THREADS=6 | ||
- | start_time_cut_polytope([" | + | #start_time_cut_polytope([" |
</ | </ | ||
=== Knapsack Integer Hulls === | === Knapsack Integer Hulls === | ||
- | Download the {{: | + | Download the {{: |
<code perl> | <code perl> | ||
$path = "/ | $path = "/ | ||
- | start_time_knapsack([" | + | ### |
+ | ## To use only one thread for normaliz set the following environment variable | ||
+ | # export OMP_NUM_THREADS=1 | ||
+ | |||
+ | start_time_knapsack([" | ||
start_time_knapsack([" | start_time_knapsack([" | ||
start_time_knapsack([" | start_time_knapsack([" | ||
## different kinds of input sorting | ## different kinds of input sorting | ||
- | ## 1=random sorting, 2=good sorting (vertices come first) | + | ## 1=random sorting, 2=vertices come first |
- | start_time_knapsack([" | + | start_time_knapsack([" |
- | start_time_knapsack([" | + | start_time_knapsack([" |
+ | |||
+ | start_time_knapsack([" | ||
+ | start_time_knapsack([" | ||
- | start_time_knapsack([" | + | start_time_knapsack([" |
+ | start_time_knapsack([" | ||
</ | </ | ||
Line 88: | Line 101: | ||
Download the {{: | Download the {{: | ||
<code perl> | <code perl> | ||
+ | # set environment: | ||
+ | |||
$path = "/ | $path = "/ | ||
+ | # no porta because coordinates are too ugly (porta does not use gmp) | ||
start_time_voronoi([" | start_time_voronoi([" | ||
- | start_time_voronoi([" | + | start_time_voronoi([" |
start_time_voronoi([" | start_time_voronoi([" | ||
- | start_time_voronoi([" | + | start_time_voronoi([" |
+ | start_time_voronoi([" | ||
## Running one example many times (1000) to check standard deviation | ## Running one example many times (1000) to check standard deviation | ||
- | stats_voronoi([" | + | #stats_voronoi([" |
</ | </ | ||
=== Symmetric Cut Polytopes === | === Symmetric Cut Polytopes === | ||
- | Download the {{: | + | Download the {{: |
<code perl> | <code perl> | ||
$n_runs = 10; | $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!) | $choose_induced_syms = 1; # uses induced symmetries of graph instead of linear symmetries of cut polytope (set to 0 for linear symmetries!) | ||
+ | |||
$path = "/ | $path = "/ | ||
foreach my $n_nodes (9,10) { | foreach my $n_nodes (9,10) { | ||
Line 126: | Line 144: | ||
## To use only one thread for normaliz set the following environment variable | ## To use only one thread for normaliz set the following environment variable | ||
# export OMP_NUM_THREADS=1 | # export OMP_NUM_THREADS=1 | ||
+ | ### | ||
+ | ## to run latte in all primal mode use the polymake command | ||
+ | # set_custom($latte_count_param=" | ||
+ | ## and restart polymake | ||
$path = "/ | $path = "/ | ||
## experiments: | ## experiments: | ||
- | $dpath = " | + | my $dpath = " |
start_time_knapsack([" | start_time_knapsack([" | ||
- | start_time_knapsack([" | + | start_time_knapsack([" |
- | start_time_knapsack([" | + | start_time_knapsack([" |
+ | start_time_knapsack([" | ||
+ | # | ||
## experiments: | ## experiments: | ||
- | $bpath = " | + | my $bpath = " |
start_time_knapsack([" | start_time_knapsack([" | ||
+ | start_time_knapsack([" | ||
+ | start_time_knapsack([" | ||
start_time_knapsack([" | start_time_knapsack([" | ||
- | |||
- | ## normaliz with higher granularity | ||
- | start_time_knapsack([" | ||
</ | </ | ||
=== Random Box === | === Random Box === | ||
- | Download the {{: | + | Download the {{: |
<code perl> | <code perl> | ||
### | ### | ||
## To use only one thread for normaliz set the following environment variable | ## To use only one thread for normaliz set the following environment variable | ||
# export OMP_NUM_THREADS=1 | # export OMP_NUM_THREADS=1 | ||
+ | ### | ||
+ | ## to run latte in all primal mode use the polymake command | ||
+ | # set_custom($latte_count_param=" | ||
+ | ## and restart polymake | ||
$path = "/ | $path = "/ | ||
start_time_rand_box([" | start_time_rand_box([" | ||
- | start_time_rand_box([" | + | start_time_rand_box([" |
start_time_rand_box([" | start_time_rand_box([" | ||
- | start_time_rand_box([" | + | start_time_rand_box([" |
+ | # 4ti2 and nmz dual disabled due to high variance, see below | ||
# | # | ||
+ | # | ||
## Running one example many times (100) to check standard deviation | ## Running one example many times (100) to check standard deviation | ||
stats_rand_box([" | stats_rand_box([" | ||
+ | stats_rand_box([" | ||
stats_rand_box([" | stats_rand_box([" | ||
- | ## Set a ulimit on time since the running times of 4ti2 have high variance | + | ## These tests produce a high variance |
+ | # | ||
+ | ## Setting | ||
# ulimit -t 3600 | # ulimit -t 3600 | ||
- | stats_rand_box([" | + | #stats_rand_box([" |
+ | </ | ||
+ | |||
+ | === Matching Polytopes === | ||
+ | Download the {{: | ||
+ | <code perl> | ||
+ | ### | ||
+ | ## To use only one thread for normaliz set the following environment variable | ||
+ | # export OMP_NUM_THREADS=1 | ||
+ | $path = "/ | ||
+ | |||
+ | start_time_matching_polytope([" | ||
+ | start_time_matching_polytope([" | ||
+ | start_time_matching_polytope([" | ||
+ | start_time_matching_polytope([" | ||
+ | start_time_matching_polytope([" | ||
+ | start_time_matching_polytope([" | ||
+ | |||
+ | ### | ||
+ | ## to run latte in all primal mode use the polymake command | ||
+ | # set_custom($latte_count_param=" | ||
+ | ## and restart polymake | ||
+ | start_time_matching_polytope([" | ||
+ | # | ||
</ | </ |