parameters = list of parameter names

This option can be used to explicitly list the parameters for a parameterized Z-polyhedral set. The default value is the list of all variables occurring in constraints, except those listed in vars; if vars is not specified, its default value is all variables occurring in constraints, so none are regarded as parameters.

parameterconstraints = list or set of linear equations and non-strict inequalities with rational number coefficients

This option can be used to impose conditions on which parameter values are included. The default value is the empty list (impose no restrictions).

lattice = lattice object, or list of a matrix and a vector

This option can be used to specify a lattice other than the default lattice, ${\mathbb{Z}}^n$. The dimension of the lattice should be the sum of the number of unknowns and the number of parameters.

A Z-polyhedral set is the intersection of a polyhedral set with an integer lattice. (A Z-polytope is the intersection of a polytope with an integer lattice; a polytope is a bounded polyhedral set.) This command constructs Maple representations of Z-polyhedral sets, possibly with parameters that occur linearly in the defining inequalities.

ZPolyhedralSet(constraints) returns the Z-polyhedral set defined by the inequalities in constraints and the lattice ${\mathbb{Z}}^n$, with the unknowns in an arbitrarily chosen order. The order of the variables can impact the efficiency of some algorithms.

ZPolyhedralSet(constraints, vars) imposes the given order on the variables. If any names in constraints are not included in vars, they are considered to be parameters. The order for the parameters is then arbitrarily chosen; this can still impact the efficiency of some algorithms, because internally some algorithms translate a parametric Z-polyhedral set to the Z-polyhedral set where all parameters are additional unknowns (ordered after the original unknowns), and the order of those unknowns then impacts efficiency.

ZPolyhedralSet(constraints, vars, parameters = params) lists the parameters explicitly, and also specifies an order on the parameters. If vars is omitted, it consists of all variables in constraints not included in params. If vars is specified, then all variables in constraints need to be listed in either vars or params.

ZPolyhedralSet(constraints, parameterconstraints = pcs) specifies conditions that involve only the parameters. If the parameters option and vars argument are not given, they default to the variables occurring in pcs and the rest of the variables in constraints, respectively; each ordered arbitrarily.

ZPolyhedralSet(constraints, lattice = L) specifies the lattice, L, that is intersected with the polyhedral set. The default lattice is ${\mathbb{Z}}^n$. L can be a Lattice object as described on the Lattice help page. Alternatively, it can be a list consisting of an $n\times n$ Matrix and an $n$-dimensional Vector, out of which Maple will construct a Lattice object as described on that same help page.

Z-polyhedral sets, or Z-polyhedra, are used to describe the integer points of a polyhedron (or polyhedral set). For more information, see the command IntegerPointDecomposition.

Note that a Z-polyhedral set can also be the input of the command IntegerPointDecomposition. In fact, a Z-polyhedral set returned by the command IntegerPointDecomposition has additional algebraic properties that an arbitrary Z-polyhedral set is unlikely to have.  Those algebraic properties are specified in Definition 2 of the first reference listed below.  They imply that such a Z-polyhedral set, say zp, is consistent (that is, has at least one point) and is specializable. This latter property means that if x is the variable of lowest rank in vars and v is a possible value for x (that is, there exists at least one point of zp with v as x-coordinate) then all the points of zp with v as x-coordinate are given by specializing at x=v the constraints of linear inequalities defining zp.

A parametric Z-Polyhedral set is a family of Z-polyhedral sets, given by a Z-polyhedral set where, in the defining linear constraints of inequalities, either the matrix or the right-hand side vector, depend linearly on parameters.  This notion is particularly useful in application problems, like parametric integer linear programming, where the feasible region, and thus the optimal solutions, depend on the values of parameters.

$\mathrm{with}\left(\mathrm{PolyhedralSets}\right)\:$

$\mathrm{with}\left(\mathrm{ZPolyhedralSets}\right)\:$

$\mathrm{eqs}≔\left[7x+12y+31z=17\,3x+5y+14z=7\right]$

$\mathrm{eqs}≔\left[7x+12y+31z=17\,3x+5y+14z=7\right]$

$\mathrm{vars}≔\left[x\,y\,z\right]$

$\mathrm{vars}≔\left[x\,y\,z\right]$

$\mathrm{zp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{eqs}\,\mathrm{vars}\right)$

$\mathrm{dec}≔\mathrm{IntegerPointDecomposition}\left(\mathrm{zp}\right)\:$

$\mathrm{newzp}≔\mathrm{dec}\left[1\right]$

$\mathrm{newzp}≔\left\{\begin{array}{lll}\text{Relations}& \:& \left\{\begin{array}{:}x=-13z-1\\ y=5z+2\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}{c}\mathrm{-13}\\ 5\\ 1\end{array}\right]\,\,\,\left[\begin{array}{c}\mathrm{-1}\\ 2\\ 0\end{array}\right]\right)\end{array}\right.$

$\mathrm{ineqs}≔\left[x+\frac{2y}{3}\le 4\,-x+y\le 1\,\frac{1}{11}x+\frac{24}{11}\le y\right]$

$\mathrm{ineqs}≔\left[x+\frac{2y}{3}\le 4\,-x+y\le 1\,\frac{x}{11}+\frac{24}{11}\le y\right]$

$\mathrm{zp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs}\,\left[x\,y\right]\right)$

$\mathrm{dec}≔\mathrm{IntegerPointDecomposition}\left(\mathrm{zp}\right)$

$\mathrm{dec}≔\left[\left\{\begin{array}{lll}\text{Relations}& \:& \left\{\begin{array}{:}x=2\\ y=3\end{array}\right.\\ \text{Variables}& \:& \left[x\,y\right]\\ \text{Parameters}& \:& \left[\right]\\ \text{ParameterConstraints}& \:& \left\{\begin{array}{}\end{array}\right.\\ \text{Lattice}& \:& \text{ZSpan}\left(\left[\begin{array}{c}0\\ 1\end{array}\right]\,\,\,\left[\begin{array}{c}2\\ 0\end{array}\right]\right)\end{array}\right.\right]$

$\mathrm{ineqs}≔\left[x+\frac{2y}{3}\le 4\,-x+y\le \frac{7}{8}\,\frac{1}{11}x+\frac{24}{11}\le y\right]$

$\mathrm{ineqs}≔\left[x+\frac{2y}{3}\le 4\,-x+y\le \frac{7}{8}\,\frac{x}{11}+\frac{24}{11}\le y\right]$

$\mathrm{zp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs}\,\left[x\,y\right]\right)$

$\mathrm{res}≔\mathrm{IntegerPointDecomposition}\left(\mathrm{zp}\right)$

$\mathrm{res}≔\left[\right]$

$\mathrm{ineqs}≔\left\{0\le x\,0\le y\,2x+3y\le 12\,3x+2y\le 12\,-x+y\le 1\right\}$

$\mathrm{ineqs}≔\left\{0\le x\,0\le y\,-x+y\le 1\,2x+3y\le 12\,3x+2y\le 12\right\}$

$\mathrm{zp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs}\,\left[x\,y\right]\right)$

$p≔\mathrm{PolyhedralSet}\left(\mathrm{ineqs}\right)$

$p≔\{\begin{array}{lll}\mathrm{Coordinates}& \:& \left[x\,y\right]\\ \mathrm{Relations}& \:& \left[-y\le 0\,-x\le 0\,-x+y\le 1\,x+\frac{2y}{3}\le 4\,x+\frac{3y}{2}\le 6\right]\end{array}$

$\mathrm{PolyhedralSet}:-\mathrm{Plot}\left(p\right)$

$\mathrm{dec}≔\mathrm{IntegerPointDecomposition}\left(\mathrm{zp}\right)\:$

$\mathrm{newzp}≔\mathrm{dec}\left[1\right]$

$\mathrm{newzp}≔\left\{\begin{array}{lll}\text{Relations}& \:& \left\{\begin{array}{:}y\le 2\\ -x\le 0\\ -y\le 0\\ -x+y\le 1\\ 3x+2y\le 12\end{array}\right.\\ \text{Variables}& \:& \left[x\,y\right]\\ \text{Parameters}& \:& \left[\right]\\ \text{ParameterConstraints}& \:& \left\{\begin{array}{}\end{array}\right.\\ \text{Lattice}& \:& \text{ZSpan}\left(\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\,\,\,\left[\begin{array}{c}0\\ 0\end{array}\right]\right)\end{array}\right.$

$\mathrm{ineqs}≔\left[\mathrm{x\_1}+3\mathrm{x\_2}\le 9-2\mathrm{theta\_1}+\mathrm{theta\_2}\,2\mathrm{x\_1}+\mathrm{x\_2}\le 8+\mathrm{theta\_1}-2\mathrm{theta\_2}\,\mathrm{x\_1}\le 4+\mathrm{theta\_1}+\mathrm{theta\_2}\,-\mathrm{x\_1}\le 0\,-\mathrm{x\_2}\le 0\right]$

$\mathrm{ineqs}≔\left[\mathrm{x\_1}+3\mathrm{x\_2}\le 9-2\mathrm{theta\_1}+\mathrm{theta\_2}\,2\mathrm{x\_1}+\mathrm{x\_2}\le 8+\mathrm{theta\_1}-2\mathrm{theta\_2}\,\mathrm{x\_1}\le 4+\mathrm{theta\_1}+\mathrm{theta\_2}\,-\mathrm{x\_1}\le 0\,-\mathrm{x\_2}\le 0\right]$

$\mathrm{vars}≔\left[\mathrm{x\_1}\,\mathrm{x\_2}\right]$

$\mathrm{vars}≔\left[\mathrm{x\_1}\,\mathrm{x\_2}\right]$

$\mathrm{paras}≔\left[\mathrm{theta\_1}\,\mathrm{theta\_2}\right]$

$\mathrm{paras}≔\left[\mathrm{theta\_1}\,\mathrm{theta\_2}\right]$

$\mathrm{pzp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs}\,\mathrm{vars}\,'\mathrm{parameters}'=\mathrm{paras}\right)$

$\mathrm{dec}≔\mathrm{IntegerPointDecomposition}\left(\mathrm{pzp}\right)$

$\mathrm{dec}≔\left[\left\{\begin{array}{lll}\text{Relations}& \:& \left\{\begin{array}{:}-\mathrm{x\_1}\le 0\\ -\mathrm{x\_2}\le 0\\ \mathrm{x\_1}-\mathrm{theta\_1}-\mathrm{theta\_2}\le 4\\ \mathrm{x\_2}-\mathrm{theta\_1}+2\mathrm{theta\_2}\le 8\\ 3\mathrm{x\_2}+2\mathrm{theta\_1}-\mathrm{theta\_2}\le 9\\ \mathrm{x\_1}+3\mathrm{x\_2}+2\mathrm{theta\_1}-\mathrm{theta\_2}\le 9\\ 2\mathrm{x\_1}+\mathrm{x\_2}-\mathrm{theta\_1}+2\mathrm{theta\_2}\le 8\end{array}\right.\\ \text{Variables}& \:& \left[\mathrm{x\_1}\,\mathrm{x\_2}\right]\\ \text{Parameters}& \:& \left[\mathrm{theta\_1}\,\mathrm{theta\_2}\right]\\ \text{ParameterConstraints}& \:& \left\{\begin{array}{:}\mathrm{theta\_2}\le 8\\ -\mathrm{theta\_2}\le 5\\ -\mathrm{theta\_1}-\mathrm{theta\_2}\le 4\\ -\mathrm{theta\_1}+2\mathrm{theta\_2}\le 8\\ 2\mathrm{theta\_1}-\mathrm{theta\_2}\le 9\end{array}\right.\\ \text{Lattice}& \:& \text{ZSpan}\left(\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right]\,\,\,\left[\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}\right]\right)\end{array}\right.\right]$

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.

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.

William Pugh. "The omega test: a fast and practical integer programming algorithm for dependence analysis." Proceedings Supercomputing ’91, pp 4–13. ACM, 1991.

William Pugh. "Counting solutions to presburger formulas: How and why." Proceedings of PLDI, pp 121–134. ACM, 1994.

The PolyhedralSets:-ZPolyhedralSets:-ZPolyhedralSet package was introduced in Maple 2023.

For more information on Maple 2023 changes, see Updates in Maple 2023.