Lee, Jon; Skipper, Daphne Computing with an algebraic-perturbation variant of Barvinok’s algorithm. (English) Zbl 1396.90049 Discrete Appl. Math. 240, 63-77 (2018). Summary: We present a variant of Barvinok’s algorithm for computing a short rational generating function for the integer points in a nonempty pointed polyhedron \(P : = \{x \in \mathbb{R}^n : A x \leq b \}\) given by rational inequalities. A main use of such a rational generating function is to count the number of integer points in \(P\). Our variant is based on making an algebraic perturbation of the right-hand side \(b \in \mathbb{Q}^m\) of the inequalities, replacing each \(b_i\) with \(b_i + \tau^i\), where \(\tau\) is considered to be an arbitrarily small positive real indeterminate. Hence, elements of our right-hand side vector become elements of the ordered ring \(\mathbb{Q} [\tau]\) of polynomials in \(\tau\). Denoting the algebraically-perturbed polyhedron as \(P(\tau) \subset \mathbb{R} [\tau]^n\), we readily see that: (i) \(P(\tau)\) is always full dimensional, (ii) \(P(\tau)\) is always simple, and (iii) \(P(\tau)\) contains the same integer points as \(P\). Unlike other versions of Barvinok’s algorithm, we will have to do some arithmetic in \(\mathbb{Q} [\tau]\). However, because of (i) we will not need to preprocess our input polyhedron if it is not full dimensional, and because of (ii) we will not need to triangulate tangent cones at the vertices of the polyhedron. We give the details of our perturbation variant of Barvinok’s algorithm, describe a proof-of-concept implementation developed in \(\mathsf{Mathematica}\), and present results of computational experiments. MSC: 90C10 Integer programming Keywords:Barvinok’s algorithm; rational generating function; polytope Software:Mathematica; cdd; GitHub; JLee_LinearOptimizationBook PDFBibTeX XMLCite \textit{J. Lee} and \textit{D. Skipper}, Discrete Appl. Math. 240, 63--77 (2018; Zbl 1396.90049) Full Text: DOI References: [1] Barvinok, A. I., A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res., 19, 4, 769-779 (1994) · Zbl 0821.90085 [2] Barvinok, A., Integer points in polyhedra, (Zurich Lectures in Advanced Mathematics (2008), European Mathematical Society (EMS): European Mathematical Society (EMS) Zürich) · Zbl 1154.52009 [3] Barvinok, A.; Pommersheim, J. E., An algorithmic theory of lattice points in polyhedra, (New Perspectives in Algebraic Combinatorics, Berkeley, CA, 1996-97. New Perspectives in Algebraic Combinatorics, Berkeley, CA, 1996-97, Math. Sci. Res. Inst. Publ., vol. 38 (1999), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 91-147 · Zbl 0940.05004 [4] Brianchon, C. J., Théorème nouveau sur les polyèdres, J. École Polytechnique, 15, 317-319 (1837) [5] Brion, M., Points entiers dans les polyèdres convexes, Ann. Sci. Éc. Norm. Supér., 21, 4, 653-663 (1988) · Zbl 0667.52011 [6] Durán, A. J.; Pérez, M.; Varona, J. L., The misfortunes of a trio of mathematicians using computer algebra systems, Can we trust them?, Notices Amer. Math. Soc., 61, 10, 1249-1252 (2014) · Zbl 1338.68299 [7] Dyer, M.; Kannan, R., On Barvinok’s algorithm for counting lattice points in fixed dimension, Math. Oper. Res., 22, 3, 545-549 (1997) · Zbl 0882.68145 [8] Emiris, I. Z.; Canny, J. F., A general approach to removing degeneracies, SIAM J. Comput., 24, 405-413 (1991) [9] K. Fukuda, cdd, http://www.inf.ethz.ch/personal/fukudak/cdd_home/; K. Fukuda, cdd, http://www.inf.ethz.ch/personal/fukudak/cdd_home/ [10] Gram, J. P., Om rumvinklerne i et polyeder, Tidsskr. Math. (Copenhagen), 4, 3, 161-163 (1874) · JFM 06.0308.02 [11] Köppe, M., A primal Barvinok algorithm based on irrational decompositions, SIAM J. Discrete Math., 21, 1, 220-236 (2007) · Zbl 1135.05003 [12] M. Köppe, S. Verdoolaege, Computing parametric rational generating functions with a primal Barvinok algorithm, Electron. J. Combin. 15.; M. Köppe, S. Verdoolaege, Computing parametric rational generating functions with a primal Barvinok algorithm, Electron. J. Combin. 15. · Zbl 1180.52014 [13] Lee, J., A First Course in Linear Optimization (2013/4/5), Reex Press, (version 2.1) https://github.com/jon77lee/JLee_LinearOptimizationBook [14] Lee, J.; Skipper, D., An algebraic-perturbation variant of Barvinok’s algorithm, (Electronic Notes in Discrete Mathematics, in: VIII Latin-American Algorithms, Graphs and Optimization Symposium, vol. 50, LAGOS (2015)), 15-20 · Zbl 1347.05088 [15] Liu, F., Perturbation of central transportation polytopes of order \(k n \times n\), (24th International Conference on Formal Power Series and Algebraic Combinatorics. 24th International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2012. 24th International Conference on Formal Power Series and Algebraic Combinatorics. 24th International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2012, Discrete Math. Theor. Comput. Sci. Proc. (2012)), 961-973 · Zbl 1412.05018 [16] Liu, F., Perturbation of transportation polytopes, J. Combin. Theory Ser. A, 120, 7, 1539-1561 (2013) · Zbl 1321.52016 [17] De Loera, J. A.; Hemmecke, R.; Köppe, M., Algebraic and geometric ideas in the theory of discrete optimization, (MOS-SIAM Series on Optimization, vol. 14 (2013), Society for Industrial and Applied Mathematics, Mathematical Optimization Society: Society for Industrial and Applied Mathematics, Mathematical Optimization Society Philadelphia, PA) · Zbl 1401.90012 [18] De Loera, J. A.; Hemmecke, R.; Tauzer, J.; Yoshida, R., Effective lattice point counting in rational convex polytopes, J. Symbolic Comput., 38, 4, 1273-1302 (2004) · Zbl 1137.52303 [19] De Loera, J. A.; Liu, F.; Yoshida, R., A generating function for all semi-magic squares and the volume of the Birkhoff polytope, J. Algebraic Combin., 30, 1, 113-139 (2009) · Zbl 1187.05009 [20] Lovász, L.; Scarf, H. E., The generalized basis reduction algorithm, Math. Oper. Res., 17, 3, 751-764 (1992) · Zbl 0774.90060 [21] Wolfram Research, Inc., Mathematica, v10.0, Champaign, 2014.; Wolfram Research, Inc., Mathematica, v10.0, Champaign, 2014. [22] Nguyen, P. Q.; Valle, B., The LLL Algorithm: Survey and Applications (2009), Springer [23] The Raspberry Pi Foundation, Raspberry Pi, http://www.raspberrypi.org/help/what-is-a-raspberry-pi/; The Raspberry Pi Foundation, Raspberry Pi, http://www.raspberrypi.org/help/what-is-a-raspberry-pi/ [24] Schönhage, A., Factorization of univariate integer polynomials by diophantine approximation and an improved basis reduction algorithm, (Automata, Languages and Programming, Antwerp, 1984. Automata, Languages and Programming, Antwerp, 1984, Lecture Notes in Comput. Sci., vol. 172 (1984), Springer: Springer Berlin), 436-447 [25] V.A. Solano, J.A. Armario-Sampalo, M.D. Frau-Garcia, P. Real-Jurado, http://library.wolfram.com/infocenter/MathSource/6621; V.A. Solano, J.A. Armario-Sampalo, M.D. Frau-Garcia, P. Real-Jurado, http://library.wolfram.com/infocenter/MathSource/6621 [26] Storjohann, A., Faster Algorithms for Integer Lattice Basis Reduction (1996), ETH Zürich [27] Szenes, A.; Vergne, M., Residue formulae for vector partitions and Euler-MacLaurin sums, Adv. Appl. Math., 30, 1-2, 295-342 (2003), Formal power series and algebraic combinatorics (Scottsdale, AZ, 2001) · Zbl 1067.52014 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.