A provable better Branch and Bound method for a nonconvex integer quadratic programming problem

摘要

This paper presents a Branch and Bound method for a nonconvex integer quadratic programming problem with a separable objective function over a bounded box. For this problem, a special branch method is constructed, which has a property that if a box has been partitioned into 2n sub-boxes, then at least one sub-box can be deleted. We analyze the complexity of the algorithm, and prove that it is better than that of the complete enumeration method in the worst case if the solution space is large enough.