geometrylinear-programmingenumeratefeasibility

find the integer points in a polyhedron


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.

Solution

  • 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.