EnumerateIntegerPoints - Maple Help

PolyhedralSets[ZPolyhedralSets]

 EnumerateIntegerPoints
 enumerate integer points in a bounded ZPolyhedralSet

 Calling Sequence EnumerateIntegerPoints(zpoly)

Parameters

 zpoly -

Description

 • EnumerateIntegerPoints(zpoly) returns a list of all the integer points in zpoly.
 • This requires zpoly to be bounded and non-parametric. If one of these assumptions does not hold, then an error is raised.

Examples

 > $\mathrm{with}\left(\mathrm{PolyhedralSets}\right):$
 > $\mathrm{with}\left(\mathrm{ZPolyhedralSets}\right):$
 > $\mathrm{ineqs}≔\left[0\le -16+2y+z,0\le -72+4x+4y+3z,0\le 2y-z,0\le -24+4x+4y-3z,0\le -4x+4y+3z,0\le 48-4x+4y-3z,0\le 48-4x-4y+3z,0\le 8-2y+z,0\le -24+4x-4y+3z,0\le 24-2y-z,0\le 24+4x-4y-3z,0\le 96-4x-4y-3z\right]$
 ${\mathrm{ineqs}}{≔}\left[{0}{\le }{-}{16}{+}{2}{}{y}{+}{z}{,}{0}{\le }{-}{72}{+}{4}{}{x}{+}{4}{}{y}{+}{3}{}{z}{,}{0}{\le }{2}{}{y}{-}{z}{,}{0}{\le }{-}{24}{+}{4}{}{x}{+}{4}{}{y}{-}{3}{}{z}{,}{0}{\le }{-}{4}{}{x}{+}{4}{}{y}{+}{3}{}{z}{,}{0}{\le }{48}{-}{4}{}{x}{+}{4}{}{y}{-}{3}{}{z}{,}{0}{\le }{48}{-}{4}{}{x}{-}{4}{}{y}{+}{3}{}{z}{,}{0}{\le }{8}{-}{2}{}{y}{+}{z}{,}{0}{\le }{-}{24}{+}{4}{}{x}{-}{4}{}{y}{+}{3}{}{z}{,}{0}{\le }{24}{-}{2}{}{y}{-}{z}{,}{0}{\le }{24}{+}{4}{}{x}{-}{4}{}{y}{-}{3}{}{z}{,}{0}{\le }{96}{-}{4}{}{x}{-}{4}{}{y}{-}{3}{}{z}\right]$ (1)
 > $L≔\mathrm{Lattice}\left(\mathrm{Matrix}\left(\left[\left[1,0,2\right],\left[0,-1,1\right],\left[0,0,2\right]\right]\right),\mathrm{Vector}\left(\left[0,0,1\right]\right)\right)$
 ${L}{≔}{\mathrm{Lattice}}{}\left(\left[\begin{array}{ccc}{1}& {0}& {2}\\ {0}& {-1}& {1}\\ {0}& {0}& {2}\end{array}\right]{,}\left[\begin{array}{c}{0}\\ {0}\\ {1}\end{array}\right]\right)$ (2)
 > $\mathrm{vars}≔\left[x,y,z\right]$
 ${\mathrm{vars}}{≔}\left[{x}{,}{y}{,}{z}\right]$ (3)
 > $\mathrm{zp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs},\mathrm{vars},\mathrm{lattice}=L\right)$
 ${\mathrm{zp}}{≔}\left\{\begin{array}{lll}{\text{Relations}}& {:}& \left\{\begin{array}{:}{0}{\le }{2}{}{y}{-}{z}\\ {0}{\le }{-}{16}{+}{2}{}{y}{+}{z}\\ {0}{\le }{8}{-}{2}{}{y}{+}{z}\\ {0}{\le }{24}{-}{2}{}{y}{-}{z}\\ {0}{\le }{-}{4}{}{x}{+}{4}{}{y}{+}{3}{}{z}\\ {0}{\le }{-}{72}{+}{4}{}{x}{+}{4}{}{y}{+}{3}{}{z}\\ {0}{\le }{-}{24}{+}{4}{}{x}{-}{4}{}{y}{+}{3}{}{z}\\ {0}{\le }{-}{24}{+}{4}{}{x}{+}{4}{}{y}{-}{3}{}{z}\\ {0}{\le }{24}{+}{4}{}{x}{-}{4}{}{y}{-}{3}{}{z}\\ {0}{\le }{48}{-}{4}{}{x}{-}{4}{}{y}{+}{3}{}{z}\\ {0}{\le }{48}{-}{4}{}{x}{+}{4}{}{y}{-}{3}{}{z}\\ {0}{\le }{96}{-}{4}{}{x}{-}{4}{}{y}{-}{3}{}{z}\end{array}\right\\\ {\text{Variables}}& {:}& \left[{x}{,}{y}{,}{z}\right]\\ {\text{Parameters}}& {:}& \left[\right]\\ {\text{ParameterConstraints}}& {:}& \left\{\begin{array}{}\end{array}\right\\\ {\text{Lattice}}& {:}& {\text{ZSpan}}\left(\left[\begin{array}{ccc}{1}& {0}& {2}\\ {0}& {-1}& {1}\\ {0}& {0}& {2}\end{array}\right]{,}{,}{,}\left[\begin{array}{c}{0}\\ {0}\\ {1}\end{array}\right]\right)\end{array}\right\$ (4)
 > $\mathrm{points}≔\mathrm{EnumerateIntegerPoints}\left(\mathrm{zp}\right)$
 ${\mathrm{points}}{≔}\left[\left[{x}{=}{9}{,}{y}{=}{6}{,}{z}{=}{5}\right]{,}\left[{x}{=}{8}{,}{y}{=}{5}{,}{z}{=}{7}\right]{,}\left[{x}{=}{9}{,}{y}{=}{5}{,}{z}{=}{7}\right]{,}\left[{x}{=}{10}{,}{y}{=}{5}{,}{z}{=}{7}\right]{,}\left[{x}{=}{7}{,}{y}{=}{6}{,}{z}{=}{7}\right]{,}\left[{x}{=}{8}{,}{y}{=}{6}{,}{z}{=}{7}\right]{,}\left[{x}{=}{9}{,}{y}{=}{6}{,}{z}{=}{7}\right]{,}\left[{x}{=}{10}{,}{y}{=}{6}{,}{z}{=}{7}\right]{,}\left[{x}{=}{11}{,}{y}{=}{6}{,}{z}{=}{7}\right]{,}\left[{x}{=}{8}{,}{y}{=}{7}{,}{z}{=}{7}\right]{,}\left[{x}{=}{9}{,}{y}{=}{7}{,}{z}{=}{7}\right]{,}\left[{x}{=}{10}{,}{y}{=}{7}{,}{z}{=}{7}\right]{,}\left[{x}{=}{8}{,}{y}{=}{5}{,}{z}{=}{9}\right]{,}\left[{x}{=}{9}{,}{y}{=}{5}{,}{z}{=}{9}\right]{,}\left[{x}{=}{10}{,}{y}{=}{5}{,}{z}{=}{9}\right]{,}\left[{x}{=}{7}{,}{y}{=}{6}{,}{z}{=}{9}\right]{,}\left[{x}{=}{8}{,}{y}{=}{6}{,}{z}{=}{9}\right]{,}\left[{x}{=}{9}{,}{y}{=}{6}{,}{z}{=}{9}\right]{,}\left[{x}{=}{10}{,}{y}{=}{6}{,}{z}{=}{9}\right]{,}\left[{x}{=}{11}{,}{y}{=}{6}{,}{z}{=}{9}\right]{,}\left[{x}{=}{8}{,}{y}{=}{7}{,}{z}{=}{9}\right]{,}\left[{x}{=}{9}{,}{y}{=}{7}{,}{z}{=}{9}\right]{,}\left[{x}{=}{10}{,}{y}{=}{7}{,}{z}{=}{9}\right]{,}\left[{x}{=}{9}{,}{y}{=}{6}{,}{z}{=}{11}\right]\right]$ (5)

References

 Rachid Seghir, Vincent Loechner, and Benoı̂t Meister. "Integer affine transformations of parametric Z-polytopes and applications to loop nest optimization." Proceedings of TACO, Vol. 9(2):8:1–8:27, 2012.
 Rui-Juan Jing and Marc Moreno Maza. "Computing the Integer Points of a Polyhedron, I: Algorithm." Proceedings of CASC 2017: 225-241, Springer.
 Rui-Juan Jing and Marc Moreno Maza. "Computing the Integer Points of a Polyhedron, II: Complexity Estimates." Proceedings of CASC 2017: 242-256, Springer.

Compatibility

 • The PolyhedralSets:-ZPolyhedralSets:-EnumerateIntegerPoints command was introduced in Maple 2023.