A new and faster representation for counting integer points in parametric polyhedra

Dmitry V. Gribanov (), Dmitry S. Malyshev (), Panos M. Pardalos () and Nikolai Yu. Zolotykh ()
Additional contact information
Dmitry V. Gribanov: Moscow Institute of Physics and Technology, Laboratory of Discrete and Combinatorial Optimization
Dmitry S. Malyshev: HSE University, Laboratory of Algorithms and Technologies for Network Analysis
Panos M. Pardalos: University of Florida, Department of Industrial and Systems Engineering
Nikolai Yu. Zolotykh: Lobachevsky State University of Nizhny Novgorod

Computational Optimization and Applications, 2025, vol. 92, issue 3, No 4, 861 pages

Abstract: Abstract In this paper, we consider the counting function $${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y) = |{{\,\mathrm{\mathcal {P}}\,}}_{y} \cap {{\,\mathrm{\mathbb {Z}}\,}}^{n_x}|$$ E P ( y ) = | P y ∩ Z n x | for a parametric polyhedron $${{\,\mathrm{\mathcal {P}}\,}}_{y} = \{ x \in {{\,\mathrm{\mathbb {R}}\,}}^{n_x} :A x \le b + B y\}$$ P y = { x ∈ R n x : A x ≤ b + B y } , where $$y \in {{\,\mathrm{\mathbb {R}}\,}}^{n_y}$$ y ∈ R n y . We give a new representation of $${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)$$ E P ( y ) , called a piece-wise step-polynomial with periodic coefficients, which is a generalization of piece-wise step-polynomials and integer/rational Ehrhart’s quasi-polynomials. It gives the fastest way to calculate $${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)$$ E P ( y ) in certain scenarios. The most important cases are the following: 1) We show that, for the parametric polyhedron $${{\,\mathrm{\mathcal {P}}\,}}_y$$ P y defined by a standard-form system $$A x = y,\, x \ge 0$$ A x = y , x ≥ 0 with a fixed number of equalities, the function $${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)$$ E P ( y ) can be represented by a polynomial-time computable function. In turn, such a representation of $${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)$$ E P ( y ) can be constructed by an $${{\,\textrm{poly}\,}}\bigl (n, \Vert A\Vert _{\infty }\bigr )$$ poly ( n , ‖ A ‖ ∞ ) -time algorithm; 2) Assuming again that the number of equalities is fixed, we show that integer/rational Ehrhart’s quasi-polynomials of a polytope can be computed by FPT-algorithms, parameterized by sub-determinants of A or its elements; 3) Our representation of $${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}$$ E P is more efficient than other known approaches, if A has bounded elements, especially if it is sparse in addition; Additionally, we provide a discussion about possible applications in the area of compiler optimization. In some “natural” assumptions on a program code, our approach has the fastest complexity bounds.

Keywords: Integer linear programming; Parametric integer programming; Short rational generating function; Bounded sub-determinants; Multidimensional knapsack problem; Subset-sum problem; Counting problem (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-024-00632-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:92:y:2025:i:3:d:10.1007_s10589-024-00632-1

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-024-00632-1

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().