| Home > Publications > Reports > Informatics (CW) |
CW 392
Sven Verdoolaege, Kevin M. Woods, Maurice Bruynooghe and Ronald Cools
Computation and manipulation of enumerators of integer projections of parametric polytopes
Abstract
Given a set of integer vectors defined by linear inequalities over a fixed number of variables, where some of the variables are considered as parameters, we consider two different ways of representing the number of elements in the set in terms of the parameters. The first is an explicit function which generalizes Ehrhart quasi-polynomials. The second is its corresponding generating function and generalizes the classical Ehrhart series. Both can be computed in polynomial time based on Barvinok's unimodular decomposition of cones. Furthermore, we can convert between the two representations in polynomial time.
In an extended problem, some of the variables that appear in the constraints may be existentially quantified and then the enumerated set corresponds to the projection of the integer points in a parametric polytope. We refer to this problem as the enumeration of the integer projection of a parametric polytope. This report shows how the enumeration of the integer projection of parametric polytopes can be reduced to the enumeration of parametric polytopes. Two approaches are described and experimentally compared. Differences are small, but both methods can solve problems that previously were considered very difficult to solve analytically.
report.pdf (1.2M) / mailto: S. Verdoolaege