# When are quadratic integer programs “easy to solve”?

Let $$N_i=\{0,1,\dots,\bar{n}_i\}$$ and define $$N=N_1\times \dots \times N_I$$. I want to maximize $$f$$ on $$N$$. $$f$$ has the following form $$f(n) = \sum_i A_i n_i -\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^2$$ where $$A_i\geq 0$$ and $$B_{ij}\geq 0$$ for all $$i,j$$. Note that $$f$$ is a quadratic and concave function when defined on $$\mathbb{R}^I$$.

I know that integer programing is in general a hard problem but I would like to find nontrivial conditions on $$A$$ and $$B$$ such that this problem is easy to solve. By easy to solve I mean that there is a procedure that is fast and that is guaranteed to find the global maximum.

### What I have tried

I have tried the following way of solving the problem. Define the mapping $$T$$ for which the $$i$$th element is defined as $$(Tn)_i=\arg\max_{\tilde{n}_i\in N_i} f\left( \left\{ n_1,\dots,\tilde{n}_i,\dots,n_I\right\}\right)$$ and iterate on $$T$$ until convergence. This is essentially a coordinate ascent algorithm but in a discrete space.

A few remarks:

1. We can look at the fixed points of $$T$$. The vector $$n^*$$ that maximizes $$f$$ is obviously a fixed point of $$T$$ (can't improve by deviating in any dimensions) but there might be multiple fixed points.
2. The mapping $$T$$ is monotone in the sense that $$n\geq n'$$ implies $$T(n)\geq T(n')$$. As a result we can use Tarski's fixed point theorem to show that the (non empty) set of fixed point is a lattice. We can find a lower bound of that set by iterating on $$T$$ from $$(0,\dots,0)$$ and an upper bound by iterating from $$(\bar{n}_1,\dots,\bar{n}_I)$$. If both procedures end up on the same vector then there is a unique fixed point and it must be $$n^*$$.
3. When it works that procedure is quite fast numerically but I don't know what conditions on $$A$$ and $$B$$ are needed for it to work.
4. Under some conditions, $$T$$ might be a contraction mapping which would guarantee uniqueness but I haven't made much progress along that path yet.

Any help is appreciated! Also, if somebody has a good reference on these problems that would be useful.