TY - JOUR

T1 - Effective lattice point counting in rational convex polytopes

AU - De Loera, Jesús A.

AU - Hemmecke, Raymond

AU - Tauzer, Jeremiah

AU - Yoshida, Ruriko

N1 - Funding Information:
We thank A. Barvinok, D. Bertsimas, D. Pasechnik, B. Sturmfels, M. Vergne, and the anonymous referees for several suggestions and useful conversations that improved this paper. This research was supported by NSF Grant DMS-0073815 and by NSF VIGRE Grant No. DMS-0135345.

PY - 2004/10

Y1 - 2004/10

N2 - This paper discusses algorithms and software for the enumeration of all lattice points inside a rational convex polytope: we describe LattE, a computer package for lattice point enumeration which contains the first implementation of A. Barvinok's algorithm (Math. Oper. Res. 19 (1994) 769). We report on computational experiments with multiway contingency tables, knapsack type problems, rational polygons, and flow polytopes. We prove that these kinds of symbolic-algebraic ideas surpass the traditional branch-and-bound enumeration and in some instances LattE is the only software capable of counting. Using LattE, we have also computed new formulas of Ehrhart (quasi-)polynomials for interesting families of polytopes (hypersimplices, truncated cubes, etc). We end with a survey of other "algebraic-analytic" algorithms, including a "homogeneous" variation of Barvinok's algorithm which is very fast when the number of facet-defining inequalities is much smaller compared to the number of vertices.

AB - This paper discusses algorithms and software for the enumeration of all lattice points inside a rational convex polytope: we describe LattE, a computer package for lattice point enumeration which contains the first implementation of A. Barvinok's algorithm (Math. Oper. Res. 19 (1994) 769). We report on computational experiments with multiway contingency tables, knapsack type problems, rational polygons, and flow polytopes. We prove that these kinds of symbolic-algebraic ideas surpass the traditional branch-and-bound enumeration and in some instances LattE is the only software capable of counting. Using LattE, we have also computed new formulas of Ehrhart (quasi-)polynomials for interesting families of polytopes (hypersimplices, truncated cubes, etc). We end with a survey of other "algebraic-analytic" algorithms, including a "homogeneous" variation of Barvinok's algorithm which is very fast when the number of facet-defining inequalities is much smaller compared to the number of vertices.

KW - Barvinok's algorithm

KW - Convex rational polyhedra

KW - Ehrhart quasi-polynomials

KW - Enumeration of lattice points

KW - Generating functions

KW - Lattice points

KW - Rational functions

UR - http://www.scopus.com/inward/record.url?scp=4344582797&partnerID=8YFLogxK

U2 - 10.1016/j.jsc.2003.04.003

DO - 10.1016/j.jsc.2003.04.003

M3 - Article

AN - SCOPUS:4344582797

SN - 0747-7171

VL - 38

SP - 1273

EP - 1302

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

IS - 4

ER -