Global extremal conditions for multi-integer quadratic programming

This paper presents a canonical duality approach to solve an integer quadratic programming problem, in which the objective function is qua-dratic and each variable may assume the value of one of p ( ≥ 3) integers. We first transform the problem into a {−1, 1} integer quadratic programming problem and then derive its “canonical dual”. It is shown that, under certain conditions, this nonconvex multi-integer programming problem is equivalent to a concave maximization dual problem over a convex feasible domain. A global optimality condition is derived and some computational examples are provided to illustrate this approach