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 quadratic 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.