find the integer points in a polyhedron

Question

Hello we have a polyhedron with the linear inequalities of its boundaries in n dimensions.

1. how to find the number of integer points in this polyhedron (exactly or approximately).
2. how to find the coordinates of the integer points in this polyhedron.

Answer 1

To give you some search terms: what you describe is an enumeration of feasible solutions to an integer program.

Last time I needed something like this, I couldn't find a ready-to-use solution, so I wrote my own implementation called “bande”. It is based on a branching algorithm, using the linear programming engine from COIN-OR to decide whether the corresponding linear (non-integer) program has any feasible solutions. Feel free to use that it it suits your need.

As to simply determining the number of lattice points: I believe there was some formula to compute that, but I don't remember any details. As far as I remember, that formula was no use in actually enumerating the solutions.

Looking at recent publications suggests that you might want to have a look at LattE.

Answer 2

Software beeing able to compute the integer points of a given polyhedron (among the convex hull) is porta.

However, all software concerning this problem base on enumerations, such that it fails for larger models.

Best regards