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.

MSC:

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