A successive domain-reduction scheme for linearly constrained quadratic integer programming problems

Abstract

A new exact solution method is developed in this paper for solving nonseparable linearly constrained quadratic integer programming problems with convex, concave or indefinite objective functions. By exploiting the special characteristics of the quadratic contour and examining the neighboring integer points of the continuous optimal solution from the continuous relaxation problem that discards the integer constraint of the original problem, cut off these sub-boxes which do not contain any optimal solution of the original problem. Integrating such solution scheme into a branch-and-bound algorithm, the proposed solution method reduces the optimality gap successively in the solution iterations. Furthermore, the proposed solution method is of a finite-step convergence, as domain cut is valid in each iteration.

Keywords:

• Quadratic integer programming problem
• optimality gap
• domain partition

Acknowledgements

The author would like to thank the anonymous referees for their valuable comments and suggestions on the earlier version of this paper.

Disclosure statement

No potential conflict of interest was reported by the author.