On counting integral points in a convex rational polytope

• 成果类型: Article
• 署名作者: Lasserre, JB; Zeron, ES
• 署名单位: Centre National de la Recherche Scientifique (CNRS); Instituto Politecnico Nacional - Mexico
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.28.4.853.20518
• 发表日期: 2003
• 页码: 853-870
• 关键词: algorithm

摘要

Given a convex rational polytope Omega(b) := {x is an element of R-+(n)\ Ax=b}, we consider the function b-->f (b), which counts the nonnegative integral points of Omega(b). A closed form expression of its Z-transform z-->F(z) is easily obtained so that f (b) can be computed as the inverse Z-transform of F. We then provide two variants of an inversion algorithm. As a by-product, one of the algorithms provides the Ehrhart polynomial of a convex integer polytope Omega. We also provide an alternative that avoids the complex integration of F(z) and whose main computational effort is to solve a linear system. This latter approach is particularly attractive for relatively small values of m, where m is the number of nontrivial constraints (or rows of A).