# Is this integer optimization problem still NP?

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?

• Welcome to OR Stack Exchange. The vector $b$ has no sign restrictions (can contain positive, negative and zero components)? Dec 16 '21 at 21:06
• hello. Yes, no sign restrictions Dec 16 '21 at 21:14

## 1 Answer

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.

• It's an interesting partial result. What do you think would be a natural next step to try? Dec 18 '21 at 3:29
• Sorry, other than trying an IP solver or maybe a constraint solver, I don't see a natural way to proceed. Dec 18 '21 at 21:51
• There are various metaheuristics you can try to use to find a feasible solution, but I don't think they are better than using an IP or CP solver in this case. Dec 18 '21 at 22:04