I'm trying to enumerate all integer points in some polytopes, but sage takes way too long.
This is a pretty minimal example of one of these polytopes.
q = MixedIntegerLinearProgram(maximization=False)
x = q.new_variable(integer=True, nonnegative=True)
q.add_constraint( x[0] == 1)
q.add_constraint(88 * x[2] == -306 * x[0] + 1 * x[1])
q.add_constraint( 1 * x[3] == 42636 * x[0] + 42 * x[1])
q.add_constraint(11 * x[4] == 30804 * x[0] + -42 * x[1])
P = q.polyhedron()
P
# A 1-dimensional polyhedron in QQ^5 defined as the convex hull of 2 vertices
P.Vrepresentation()
# (A vertex at (1, 34/7, 5134/7, 73440, 0), A vertex at (1, 0, 306, 55488, 1632))
Now, I would like to enumerate the integral points in this (1-dimensional) polytope. Looking at the second coordinate of the two boundary points, it is clear there can be at most five such points (in fact, there are exactly five).
However, P.integral_points() seems to take forever.
Is there anything I can do to speed this up? I would like to do similar problems that are higher-dimensional, and have a lot more constraints (bounding hyperplanes).
Earlier, I used a MILP library (COIN) to solve the system, giving one integer point, then further constrain the system to exclude this solution, solve again, etc. This is fast enough for this particular example, but becomes unfeasible when the dimension of the polytope and/or the number of integer points increases.
