Global extremal conditions for multi-integer quadratic programming. (English) Zbl 1161.90457

Summary: 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 (\geq 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.


90C20 Quadratic programming
90C10 Integer programming
90C46 Optimality conditions and duality in mathematical programming
Full Text: DOI Link