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

Wang, Zhenbo; Fang, Shu-Cherng; Gao, David Y.; Xing, Wenxun

J. Ind. Manag. Optim. 4, No. 2, 213-225 (2008).

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

Keywords:

global optimization; quadratic programming; duality theory