A polynomial case of convex integer quadratic programming problems with box integer constraints

In this paper, we study a special class of convex quadratic integer programming problem with box constraints. By using the decomposition approach, we propose a fixed parameter polynomial time algorithm for such a class of problems. Given a problem with size $$n$$ n being the number of decision variables and $$m$$ m being the possible integer values of each decision variable, if the $$n-k$$ n - k largest eigenvalues of the quadratic coefficient matrix in the objective function are identical for some $$k$$ k $$(0>k>n)$$ ( 0 > k > n ) , we can construct a solution algorithm with a computational complexity of $${\mathcal {O}}((mn)^k)$$ O ( ( m n ) k ) . To achieve such complexity, we decompose the original problem into several convex quadratic programming problems, where the total number of the subproblems is bounded by the number of cells generated by a set of hyperplane arrangements in $$\mathbb {R}^k$$ R k space, which can be efficiently identified by cell enumeration algorithm. Copyright Springer Science+Business Media New York 2015