Showing that a polyhedron doesn't contain an integral point

Question

I have the following question: I have to decide if a polytope $P = \{x\in\mathbb{R}_{\geq 0}^{\ell}\mid Ax=0\}$ contains an integral point except $x=0$, for hundreds or thousands of different matrices $A$ (some also huge). So my approach was to solve the optimization problem

\begin{align*} \rm{max}\quad &0\\ \rm{s.t.}\quad &x \in P \cap \mathbb{Z}^\ell\\ & x\neq 0 \end{align*} and check this for infeasiblity. For this I use a solver like CPLEX or similar. Now my question: How reliable is the result? If CPLEX answers "infeasible", can I be absolutely sure that there is no integral point in $P$?

Additionally, is there a better approach for this?

I haven't found anything on the reliability, so I would be very happy if someone could answer this or give a source where I can read something on that!

Answer 1

You can formulate $x \neq 0$ as $\sum_i x_i \geq 1$.

The algorithms used by CPLEX to determine feasibility (branch&bound and cutting planes, combined with the simplex or barrier method) are guaranteed to give the correct answer. Any book on combinatorial optimization proves that. However, the implementation of those algorithms in CPLEX is limited by numerical precision, so neither a feasible or infeasible result is reliable.

A feasible result is easy to check yourself. For an infeasible instance, you could enable just the cutting plane algorithm and request the cutting planes and certificate of infeasibility from CPLEX to validate the answer with arbitrary precision arithmetic. I suspect that you will find that the certificate is invalid, but it's worth trying.

Answer 2

The reliability of a declaration of infeasibility will depend on numeric properties of A and its submatrices. CPLEX has a parameter that you can use to tell it to pay extra attention to numerical issues (at the cost of slowing it down). Even that is not a guarantee, though. With floating point arithmetic, there are no absolute certainties.

You might also pay attention to the constraint tolerance. CPLEX will accept $x$ as satisfying $a'x=0$ if $|a'x|\le \epsilon$, where $\epsilon > 0$ is a parameter you can tweak. Similarly, it accepts $x_j$ as integer-valued if $x_j$ is within $\delta > 0$ of the nearest integer, where $\delta$ is another parameter you can tweak. Generally speaking, the larger you make $\epsilon$ and $\delta$, the more credible a claim of infeasibility is, but that too comes at a cost: if you increase the parameters and CPLEX says it has a feasible solution, you will need to check the solution and, if not really feasible, solve the model again with tighter parameter values.