On counting integral points in a convex rational polytope

On counting integral points in a convex rational polytope

0.00 Avg rating0 Votes
Article ID: iaor20072111
Country: United States
Volume: 28
Issue: 4
Start Page Number: 853
End Page Number: 870
Publication Date: Nov 2003
Journal: Mathematics of Operations Research
Authors: ,
Abstract:

Given a convex rational polytope Ω(b):={x∈ℝn+ | Ax=b}, we consider the function b ↦ f(b), which counts the nonnegative integral points of Ω(b). A closed form expression of its ℤ-transform z ↦ ℱ(z) is easily obtained so that f(b) can be computed as the inverse ℤ-transform of ℱ. 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 Ω. We also provide an alternative that avoids the complex integration of ℱ(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).

Reviews

Required fields are marked *. Your email address will not be published.