An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs

This paper addresses a new continuous approach based on the DC (Difference of Convex functions) programming and DC algorithms (DCA) to Binary quadratic programs (BQP) which play a key role in combinatorial optimization. DCA is completely different from other avalaible methods and featured by generating a convergent finite sequence of feasible binary solutions (obtained by solving linear programs with the same constraint set) with decreasing objective values. DCA is quite simple and inexpensive to handle large-scale problems. In particular DCA is explicit, requiring only matrix-vector products for Unconstrained Binary quadratic programs (UBQP), and can then exploit sparsity in the large-scale setting. To check globality of solutions computed by DCA, we introduce its combination with a customized Branch-and-Bound (BB) scheme using DC/SDP relaxation. The combined algorithm allows checking globality of solutions computed by DCA and restarting it if necessary and consequently accelerates the BB approach. Numerical results on several series test problems , show the robustness and efficiency of our algorithm with respect to standard methods. In particular DCA provides epsiv;-optimal solutions in almost all cases after only one restarting and the combined DCA-BB-SDP always provides (ϵ-)optimal solutions.