Number of lattices inside mixed-integer polyhedron

26 Views Asked by At

Given a mixed-integer polyhedron

$P = \{(x;z) \in \mathbb{R}^n \times \mathbb{Z}^d \mid A x + B z \leq c \}$

with $A \in \mathbb{Q}^{m \times n}$, $B \in \mathbb{Q}^{m \times d}$ and $c \in \mathbb{Q}^{m}$, is $\textrm{proj}_{\mathbb{Z}^d} (P)$ a set with a finite number of elements? That should be equivalent to say that the number of lattices (i.e., "integer points") inside $P$ is finite, right? If the answer is yes, are there some ways to enumerate them?

1

There are 1 best solutions below

0
On BEST ANSWER

If $P$ is bounded (hence compact), then the projection has finite cardinality. If $P$ is unbounded, then you cannot really say. It is easy to construct unbounded examples that are empty (no integer-feasible points), and it is easy to construct unbounded examples with an infinite number of integer-feasible points.

If $P$ is bounded, it is possible (given enough time and memory) to enumerate all integer feasible solutions using a MIP solver. CPLEX has a solution pool feature that, if properly configured, will do this. Alternatively, if you recode all the integer variables into linear combinations of binary variables, you can solve for any feasible solution (set the object to minimize or maximize 0), record it, add a "no-good" constraint that cuts it out (and only that one), and iterate ad nauseum. I think you can also do this with a good quality constraint solver.

That said, enumerating all points in the projection can easily overwhelm you in terms of time and memory.