Base class for polyhedra over \(\QQ\)

class sage.geometry.polyhedron.base_QQ.Polyhedron_QQ(parent, Vrep, Hrep, **kwds)

Bases: sage.geometry.polyhedron.base.Polyhedron_base

Base class for Polyhedra over \(\QQ\)

integral_points_count(verbose=False, use_Hrepresentation=False, explicit_enumeration_threshold=1000, preprocess=True, **kwds)

Return the number of integral points in the polyhedron.

This method uses the optional package latte_int if an estimate for lattice points based on bounding boxes exceeds explicit_enumeration_threshold.

INPUT:

  • verbose (boolean; False by default) – whether to display verbose output.
  • use_Hrepresentation - (boolean; False by default) – whether to send the H or V representation to LattE
  • preprocess - (boolean; True by default) – whether, if the integral hull is known to lie in a coordinate hyperplane, to tighten bounds to reduce dimension

See also

latte the interface to LattE interfaces

EXAMPLES:

sage: P = polytopes.cube()
sage: P.integral_points_count()
27
sage: P.integral_points_count(explicit_enumeration_threshold=0) # optional - latte_int
27

We enlarge the polyhedron to force the use of the generating function methods implemented in LattE integrale, rather than explicit enumeration.

sage: (1000000000*P).integral_points_count(verbose=True) # optional - latte_int This is LattE integrale… … Total time:… 8000000012000000006000000001

We shrink the polyhedron a little bit:

sage: Q = P*(8/9)
sage: Q.integral_points_count()
1
sage: Q.integral_points_count(explicit_enumeration_threshold=0) # optional - latte_int
1

Unbounded polyhedra (with or without lattice points) are not supported:

sage: P = Polyhedron(vertices=[[1/2, 1/3]], rays=[[1, 1]])
sage: P.integral_points_count()
Traceback (most recent call last):
...
NotImplementedError: ...
sage: P = Polyhedron(vertices=[[1, 1]], rays=[[1, 1]])
sage: P.integral_points_count()
Traceback (most recent call last):
...
NotImplementedError: ...

“Fibonacci” knapsacks (preprocessing helps a lot):

sage: def fibonacci_knapsack(d, b, backend=None):
....:     lp = MixedIntegerLinearProgram(base_ring=QQ)
....:     x = lp.new_variable(nonnegative=True)
....:     lp.add_constraint(lp.sum(fibonacci(i+3)*x[i] for i in range(d)) <= b)
....:     return lp.polyhedron(backend=backend)
sage: fibonacci_knapsack(20, 12).integral_points_count() # does not finish with preprocess=False
33