Wolfram Library Archive


All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

Algebraic Perturbation Barvinok
Authors

Daphne Skipper
Organization: Augusta University
Department: Mathematics
Jon Lee
Organization: University of Michigan
Department: Industrial and Operations Engineering Department
Revision date

2015-12-07
Description

This algorithm generates a short rational generating function G(z) for a bounded input polyhedron P defined by a system of rational linear inequalities Ax <= b. This variation of Barvinok`s algorithm operates on an algebraic perturbation P(t) of the original polyhedron P, created so that P(t) is both full dimensional and has all simple vertices. As an option, the algorithm uses G(z) to count the integer points of P. For a complete description of the algorithm, see 1) Jon Lee, Daphne Skipper. An algebraic-perturbation variant of Barvinok's algorithm. LAGOS 2015, To appear in: Electronic Notes in Discrete Mathematics. 2) Jon Lee, Daphne Skipper. Computing with an algebraic-perturbation variant of Barvinok's algorithm. To appear in: Discrete Applied Mathematics.
Subjects

*Applied Mathematics > Optimization
*Mathematics > Discrete Mathematics
*Mathematics > Geometry > n-Dimensional Geometry
Keywords

Barvinok’s algorithm, rational generating function, integer points, lattice point enumeration, polytope, polyhedron, linear integer optimization
Downloads Download Wolfram CDF Player

Download
AlgebraicPerturbationBarvinok.m (16.8 KB) - Mathematica Package