Integer Linear Programming Decision Problem

Definition

Integer Linear Programming Decision Problem

Instance: An integer matrix $A\in {\mathbb{Z}}^{m\times n}$, vectors $b\in {\mathbb{Z}}^m$, $c\in {\mathbb{Z}}^n$, and a threshold $t\in \mathbb{Z}$, all encoded in binary.

Question: Does there exist $x\in {\mathbb{Z}}^n$ such that

$$Ax\le b\text{and}{c}^{\top }x\ge t?$$

The inequality $Ax\le b$ holds row by row. This asks whether integer linear programming has a feasible integer solution reaching the objective threshold. Pure integer feasibility is the special case $c=0$ and $t=0$.