Pham Dinh Tao, Nguyen Canh Nam, Le Thi Hoai An: "An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs".

Abstract: 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 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 B&B approach. Numerical results on several series test problems provided in OR-Library (Beasley in J Global Optim, 8:429–433, 1996), show the robustness and efficiency of our algorithm with respect to standard methods. In particular DCA provides ϵ-optimal solutions in almost all cases after only one restarting and the combined DCA-B&B-SDP always provides (ϵ−)optimal solutions. 

 

Keywords: DC programming, DC algorithms (DCA), Nonconvex quadratic programming, Exact penalty, DC relaxation, Branch-and-bound (B&B), Semidefinite programming (SDP), Binary quadratic programming (BQP).

 

Citation: Pham Dinh Tao, Nguyen Canh Nam, Le Thi Hoai An, An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs, J. Global Optimization, Volume 48, Number 4, pp. 595-632, 2010.

 

Download link