Convex reformulation for binary quadratic programming problems via average objective value maximization.

Quadratic convex reformulation is an important method for improving the performance of a branch-and-bound based binary quadratic programming solver. In this paper, we study a new convex reformulation method. By this reformulation, the efficiency of a branch-and-bound algorithm can be improved significantly. We also compare this new reformulation method with other proposed methods, whose effectiveness has been proven. Numerical experimental results show that our reformulation method performs better than the compared methods for certain types of binary quadratic programming problems. [ABSTRACT FROM AUTHOR]