Is this integer optimization problem still NP?

Question

I have the following integer optimization problem \begin{align}\min&\quad\sum_ix_i\\ \text{s.t.}&\quad Ax \geq b\\ &\quad x \geq 0,\\ &\quad x \in \mathbb{Z}^n\end{align} where $b$ is a general vector of integers, $A$ is an $n$ by $n$ matrix where all entries are integers, but it has a very specific format: it is symmetric, every entry in the main diagonal is equal to the opposite of the sum of its row/column except when $i=j$, and if $i \neq j$, $A_{ij}$ is either 0 or 1. I will try to write that more formally.

\begin{align}A_{ij} &\in \{0, 1\}\quad\text{if}\quad i \neq j\\A_{ii} &= -\sum_{j=0,j \neq i}^{n-1}A_{ij} = -\sum_{j=0,j \neq i}^{n-1}A_{ji}\end{align}

Example of $A$: $$ \begin{bmatrix} -3 & 1 & 1 & 0 & 1\\ 1 & -3 & 1 & 1 & 0\\ 1 & 1 & -3 & 0 & 1\\ 0 & 1 & 0 & -2 & 1\\ 1 & 0 & 1 & 1 & -3\\ \end{bmatrix} $$ According to wikipedia, a general ILP is NP-hard. How do I:

1. Prove this specific format is still NP-hard (probably by some reduction) or find that this is a special case that can be solved in polynomial time?

2. Find if it's feasible without actually solving the optimization problem?

Answer 1

Here is a partial answer to the feasibility question. Let $e\in \mathbb{R}^n$ be a vector with all components equal to 1. $Ax\ge b \implies e'Ax \ge e'b.$ Since $e'A=0,$ if the problem is feasible you must have $e'b\le 0.$ So if the sum of the components of $b$ is positive, the problem is infeasible.