A new branch and bound algorithm for integer quadratic programming problems

作者：Ma, Xiaohua; Gao, Yuelin^*; Liu, Xia

来源：Journal of Nonlinear Sciences and Applications, 2016, 9(3): 1153-1164.

DOI：10.22436/jnsa.009.03.42

• Integer quadratic programming
• branch and bound
• linear relaxation
• rectangular deep bisection
• rectangular reduction

For integer quadratic programming problems, a new branch and bound algorithm is proposed in this paper through a series of improvements on the traditional branch and bound algorithm, which can be used to solve integer quadratic programming problems effectively and efficiently. This algorithm employs a new linear relaxation and bound method and a rectangular deep bisection method. At the same time, a rectangular reduction strategy is used to improve the approximation degree and speed up the convergence of the algorithm. Numerical results show that the proposed algorithm is feasible and effective and has improved the existing relevant branch and bound algorithms.

• 出版日期2016
• 单位北方民族大学