Simple Explicit Formula for Counting Lattice Points of Polyhedra

DOI10.1007/978-3-540-72792-7_28MaRDI QIDQ5429280zbMATH OpenOpenAlexFDO

Authors E. S. Zeron, Jean B. Lasserre

Publication date 29 November 2007

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0702406

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: Given $zin{C}^n$ and $Ain{Z}^{mimesn}$, we consider the problem of evaluating the counting function $h(y;z):=sum{z}^x:xin{Z}^n;Ax=y,xgeq0$. We provide an explicit expression for $h(y;z)$ as well as an algorithm with possibly numerous but very simple calculations. In addition, we exhibit finitely many fixed convex cones, explicitly and exclusively defined by $A$, such that for any $yin{Z}^m$, the sum $h(y;z)$ can be obtained by a simple formula involving the evaluation of $sum{z}^x$ over the integral points of those cones only. At last, we also provide an alternative (and different) formula from a decomposition of the generating function into simpler rational fractions, easy to invert.

Recommendations

• An Alternative Algorithm for Counting Lattice Points in a Convex Polytope
• Counting lattice points of rational polyhedra
• On Counting Lattice Points in Polyhedra
• On Counting Integral Points in a Convex Rational Polytope
• The many aspects of counting lattice points in polytopes

Cited in

(5)

• Fibers of multi-way contingency tables given conditionals: relation to marginals, cell bounds and Markov bases
• Computing Optimized Path Integrals for Knapsack Feasibility
• On Counting Integral Points in a Convex Rational Polytope
• An Alternative Algorithm for Counting Lattice Points in a Convex Polytope
• A new and faster representation for counting integer points in parametric polyhedra

This page was built for publication: Simple Explicit Formula for Counting Lattice Points of Polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5429280)