ZOE → ILP

In ILP

• we look for integer vector $\vec{x}$ that satisfies $A\vec{x} \le \vec{b}$.

There’s an instance of ZOE in the precise form

Rewrite each equation of ZOE instance as two inequalities, and to add for each variable $x_i$, the inequalities $x_i \le 1, -x_i \le 0$

Therefore ILP can be viewed as a generalization of ZOE problem, so therefore ILP is NP-complete