A faster algorithm for counting the integer points number in $\Delta$-modular polyhedra

D. Gribanov ; D. Malyshev

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 613-626.

Résumé

Let a polytope $\mathcal{P}$ be defined by a system $A x \leq b$. We consider the problem to count a number of integer points inside $\mathcal{P}$, assuming that $\mathcal{P}$ is $\Delta$-modular. The polytope $\mathcal{P}$ is $\Delta$-modular if all the rank sub-determinants of $A$ are bounded by $\Delta$ in the absolute value. We present a new FPT-algorithm, parameterized by $\Delta$ and by the number of simple cones in the normal fun triangulation of $\mathcal{P}$, which is more efficient for $\Delta$-modular problems, than the approach of A. Barvinok et al. [1, 2, 3, 4, 5]. To this end, we do not directly compute the short rational generating function for $\mathcal{P} \cap \mathbb{Z}^n$, which is commonly used for the considered problem. We compute its particular representation in the form of exponential series that depends on one variable, using the dynamic programming principle. We completely do not use the A. Barvinok's unimodular sign decomposition technique. Using our new complexity bound, we consider different special cases that may be of independent interest. For example, we give FPT-algorithms for counting the integer points number in $\Delta$-modular simplicies and similar polytopes that have $n + O(1)$ facets. For any fixed $m$, we give an FPT-algorithm to count solutions of the unbounded $m$-dimensional $\Delta$-modular knapsack problem. For the case, when $\Delta$ grows slowly with respect to $n$, we give a counting algorithm, which is more effective, than the state of the art ILP feasibility algorithm due to [6, 7].

Détail

Keywords: integer linear programming, short rational generating function, bounded sub-determinants, multidimensional knapsack problem, subset-sum problem, counting problem.

Bibliographie

[1] A. Barvinok, Integer Points in Polyhedra, European Mathematical Society, Zürich, 2008 | MR | Zbl

[2] A. Barvinok, J. Pommersheim, “An algorithmic theory of lattice points in polyhedra”, New perspectives in algebraic combinatorics, eds. Billera Louis J. (ed.) et al., Cambridge University Press, Cambridge, 1999, 91–147 | MR | Zbl

[3] A. Barvinok, K. Woods, “Short rational generating functions for lattice point problems”, J. Am. Math. Soc., 16:4 (2003), 957–979 | DOI | MR | Zbl

[4] M. Dyer, K. Ravi, “On Barvinok's algorithm for counting lattice points in fixed dimension”, Math. Oper. Res., 22:3 (1997), 545–549 | DOI | MR | Zbl

[5] M. Köppe, S. Verdoolaege, “Computing parametric rational generating functions with a primal Barvinok algorithm”, Electron. J. Comb., 15:1 (2008), R16 | DOI | MR | Zbl

[6] D. Dadush, Integer programming, lattice algorithms, and deterministic volume estimation, Georgia Institute of Technology, ProQuest Dissertations Publishing, Ann Arbor, 2012 | MR

[7] D. Dadush, C. Peikert, S. Vempala, “Enumerative lattice algorithms in any norm via M-ellipsoid coverings”, Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science, FOCS 2011 (Palm Springs, CA, USA, October 22-25 2011), ed. Ostrovsky Rafail, IEEE Computer Society, Los Alamitos, 2011, 580–589 | DOI | MR | Zbl

[8] J. Lee, J. Paat, I. Stallknecht, L. Xu, Polynomial upper bounds on the number of differing columns of an integer program, 2021, arXiv: 2105.08160

[9] P. McMullen, “The maximum numbers of faces of a convex polytope”, Mathematika, Lond., 17:2 (1970), 179–184 | DOI | MR | Zbl

[10] A. Chirkov, D. Gribanov, D. Malyshev, P. Pardalos, S. Veselov, N. Zolotykh, “On the complexity of quasiconvex integer minimization problem”, J. Glob. Optim., 73:4 (2019), 761–788 | DOI | MR | Zbl

[11] D. Gribanov, D. Malyshev, “Integer conic function minimization based on the comparison oracle”, Mathematical optimization theory and operations research, 18th international conference, MOTOR 2019, Proceedings, eds. Khachay Michael (ed.) et al., Springer, Cham, 2019, 218–231 | DOI | MR | Zbl

[12] S. Veselov, D. Gribanov, N. Zolotykh, A. Chirkov, “A polynomial algorithm for minimizing discrete convic functions in fixed dimension”, Discrete Appl. Math., 283 (2020), 11–19 | DOI | MR | Zbl

[13] D. Gribanov, N. Zolotykh, “On lattice point counting in $\Delta$-modular polyhedra”, Optimization Letters, 2021 | MR

[14] D. Gribanov, I. Shumilov, D. Malyshev, P. Pardalos, “On $\Delta$-modular integer linear problems in the canonical form and equivalent problems”, 2021, arXiv: 2002.01307v5

[15] S. Veselov, “The proof of a generalization of Borosh–Treybig's hypothesis for Diophantine equations”, Diskretn. Anal. Issled. Oper., Ser. 1, 8:1 (2001), 17–22 | MR | Zbl

[16] F. Eisenbrand, C. Hunkenschröder, Kim-Manuel Klein, M. Kouteckỳ, A. Levin, S. Onn, An algorithmic theory of integer programming, 2019, arXiv: 1904.01361

[17] T. Gavenčiak, M. Kouteckỳ, D. Knop, “Integer programming in parameterized complexity: Five miniatures”, Discrete Optimization, 2020, 100596 | MR

[18] A. Barvinok, “A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed”, Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, 1993, 566–572 | DOI | MR

[19] M. Beck, S. Robins, Computing the continuous discretely. Integer-point enumeration in polyhedra. With illustrations by David Austin, Springer, New York, 2015 | MR | Zbl

[20] J. De Loera, R. Hemmecke, M. Köppe, Algebraic and geometric ideas in the theory of discrete optimization, Society for Industrial and Applied Mathematics, Philadelphia, 2013 | MR | Zbl

[21] J.B. Lasserre, Linear and integer programming vs linear integration and counting. A duality viewpoint, Springer, New York, 2009 | MR | Zbl

[22] D. Micciancio, P. Voulgaris, “A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations”, SIAM J. Comput., 42:3 (2013), 1364–1391 | DOI | MR | Zbl

[23] J.B. Lasserre, E. Zeron, “Simple explicit formula for counting lattice points of polyhedra”, International Conference on Integer Programming and Combinatorial Optimization, 2007, 367–381 | MR

[24] M. Beck, “Counting lattice points by means of the residue theorem”, Ramanujan J., 4:3 (2000), 299–310 | DOI | MR | Zbl

[25] M. Beck, “The partial-fractions method for counting solutions to integral linear systems”, Discrete Comput. Geom., 32:4 (2004), 437–446 | DOI | MR | Zbl

[26] M. Beck, S. Robins, “Explicit and efficient formulas for the lattice point count in rational polygons using Dedekind-Rademacher sums”, Discrete Comput. Geom., 27:4 (2002), 443–459 | DOI | MR | Zbl

[27] E. Daues, U. Friedrich, “Computing Optimized Path Integrals for Knapsack Feasibility”, INFORMS Journal on Computing, 2022 | MR

[28] U. Friedrich, Solving IP via complex integration on shortest paths, 2020 www.optimization-online.org/DB_HTML/2020/06/7848.html

[29] H. Hirai, R. Oshiro, K. Tanaka, “Counting integral points in polytopes via numerical analysis of contour integration”, Math. Oper. Res., 45:2 (2020), 455–464 | DOI | MR | Zbl

[30] J.B. Lasserre, E. Zeron, “Solving the knapsack problem via Z-transform”, Oper. Res. Lett., 30:6 (2002), 394–400 | DOI | MR | Zbl

[31] J.B. Lasserre, E. Zeron, “An alternative algorithm for counting lattice points in a convex polytope”, Math. Oper. Res., 30:3 (2005), 597–614 | DOI | MR | Zbl

[32] J.B. Lasserre, E. Zeron, “On counting integral points in a convex rational polytope”, Math. Oper. Res., 28:4 (2003), 853–870 | DOI | MR | Zbl

[33] Y. Nesterov, Fast Fourier transform and its applications to integer knapsack problems, CORE Discussion Paper No 2004/64, 2004

[34] M. Brion, M. Vergne, “Lattice points in simple polytopes”, J. Am. Math. Soc., 10:2 (1997), 371–392 | DOI | MR | Zbl

[35] M. Brion, M. Vergne, “Residue formulae, vector partition functions and lattice points in rational polytopes”, J. Am. Math. Soc., 10:4 (1997), 797–833 | DOI | MR | Zbl

[36] F. Eisenbrand, R. Weismantel, “Proximity results and faster algorithms for integer programming using the Steinitz lemma”, ACM Trans. Algorithms, 16:1 (2020), 5 | DOI | MR | Zbl

[37] K. Jansen, L. Rohwedder, On integer programming, discrepancy, and convolution, 2018, arXiv: 1803.04744 | MR

[38] P. McMullen, “Valuations and dissections”, Handbook of convex geometry, v. B, eds. Gruber P. M. (ed.) et al., North-Holland, Amsterdam, 1993, 933–988 | DOI | MR | Zbl

[39] P. McMullen, R. Schneider, “Valuations on convex bodies”, Convexity and its applications, Collect. Surv., 1983, 170–247 | DOI | MR | Zbl

[40] J. Lawrence, “Rational-function-valued valuations on polyhedra”, Discrete and computational geometry, Proc. DIMACS Spec. Year Workshops 1989-90, DIMACS, Ser. Discret. Math. Theor. Comput. Sci., 6, 1991, 199–208 | DOI | MR | Zbl

[41] A. Pukhlikov, A. Khovanskii, “The Riemann-Roch theorem for integrals and sums of quasipolynomials on virtual polytopes”, St. Petersbg. Math. J., 4:4 (1993), 789–812 | MR | Zbl

[42] M. Brion, “Points entiers dans les polyèdres convexes”, Ann. Sci. Éc. Norm. Supér.(4), 21:4 (1988), 653–663 | DOI | MR | Zbl

[43] D. Avis, K. Fukuda, “A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra”, Discrete Comput. Geom., 8:3 (1992), 295–313 | DOI | MR | Zbl

[44] A. Storjohann, “Near optimal algorithms for computing Smith normal forms of integer matrices”, Proceedings of the 1996 international symposium on symbolic and algebraic computation, ISSAC '96 (Zürich, Switzerland, July 24-26, 1996), ed. Lakshman Y. N., ACM Press, New York, 1996, 267–274 | DOI | Zbl

[45] B. Grünbaum, Convex polytopes, Graduate Texts in Mathematics, 221, Springer, New York, 2003 | MR | Zbl

[46] W. Cook, A.M.H. Gerards, A. Schrijver, É. Tardos, “Sensitivity theorems in integer linear programming”, Math. Program., 34:3 (1986), 251–264 | DOI | MR | Zbl