Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
researchdata:polymakeilp [2015/11/10 15:54] – [Integer Points] assarf | user_guide:tutorials:polymakeilp [2019/01/29 21:46] (current) – external edit 127.0.0.1 | ||
---|---|---|---|
Line 4: | Line 4: | ||
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 74: | Line 74: | ||
=== Knapsack Integer Hulls === | === Knapsack Integer Hulls === | ||
- | Download the {{: | + | Download the {{: |
<code perl> | <code perl> | ||
$path = "/ | $path = "/ | ||
Line 117: | Line 117: | ||
=== Symmetric Cut Polytopes === | === Symmetric Cut Polytopes === | ||
- | Download the {{: | + | Download the {{: |
<code perl> | <code perl> | ||
$n_runs = 10; | $n_runs = 10; | ||
Line 168: | Line 168: | ||
=== Random Box === | === Random Box === | ||
- | Download the {{: | + | Download the {{: |
<code perl> | <code perl> | ||
### | ### | ||
Line 200: | Line 200: | ||
=== Matching Polytopes === | === Matching Polytopes === | ||
- | Download the {{: | + | Download the {{: |
<code perl> | <code perl> | ||
### | ### |