# Unconstrained convex quadratic integer programing

Let $$N_i=\{0,1,\dots,\bar{n}_i\}$$ and define $$N=N_1\times \dots \times N_I$$. I have a minimization problem of the form $$\min_{n\in 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$$. This problem can be written as a convex quadratic integer program.

What are the standard algorithms to solve these problems numerically? Are they guaranteed to find a global solution? How fast are they?

• This seems like a misnomer to me. According to Boyd and Vandenberghe, a Convex Optimization problem is an optimization problem whose domain is a convex set. But an integer programming problem is one where the solutions must be integers. The set of integers is not convex. – NicNic8 Jan 10 at 20:16
• Yes, I know that using the word "convex" here is a bit tricky but several people in the literature use convex in this way for integer programs. – user_lambda Jan 10 at 20:17
• Typically, a mixed integer nonlinear programming problem (MINLP) whose continuous relaxation is convex is referred to as a "Convex MINLP" This is terminology that's been around for at least 25 years... – Brian Borchers Jan 10 at 20:45
• Your terminology is fine. You would think it might be possible to exploit the fact that it is unconstrained (that is, beyond the integrality constraints), but I'm not seeing it. – Michael Grant Jan 12 at 2:56