A new branch and bound method with pretreatment for the binary quadratic programming

摘要

A new branch and bound algorithm with pretreatment for the binary quadratic programming is presented in this paper. Firstly, we use pretreatment method to decrease the size of the binary quadratic programming. Then, based on the pretreatment method, A new branch and bound algorithm is proposed, which give the new method for the initial solution, the new bounding method, and the new pruning regulation. Numerical experiments demonstrate the algorithm is simple, fast, and efficient.