Study On The Algorithms And Applications Of The Binary Quadratic Programming

Binary quadratic programming is one of the important integral programming problems. Many classical combinatorial optimization problems are the special examples, such as the max cut problem, the max bisection problem, and the max clique problem etc. It has a variety of applications such as VLSI design, statistical physics, financial analysis, multiuser detection and signal processing etc. It is very interesting and valuable to study the algorithms and applications of the binary quadratic programming.Binary quadratic programming is one of the NP-hard problems, which has not global optimal algorithms in polynomial time. The paper studies some approximate algorithms and some optimal algorithms with pretreatment for the binary quadratic programming, and the algorithms are applied to the multiuser detection problem and the design of the FIR digital filters. The main contributions are listed as follows.1. Based on the semidefinite programming relaxation of the binary quadratic programming, the equivalent nonlinear programming model is obtained by use of the matrix factorization technique and the low rank factorization technique. A successive linear programming algorithm and a successive quadratic programming algorithm are presented for the nonlinear programming model. Furthermore, its global convergence result is given in some conditions. Coupled with the randomized method, they provide better suboptimal solutions. The numerical examples to the max cut problem and the max bisection problem show that our method has the advantage of lower EMS memory and of lesser CPU time than the inner-point method for the semidefinite programming relaxation, especially for the large scale semidefinite programming.2. Based on the characteristic and the global optimal condition of the binary quadratic programming, a pretreatment algorithm is proposed. Most of the elements of the optimal solution to the binary quadratic programming can be determined by the pretreatment algorithm, so the problem is converted to a binary quadratic programming problem with a lesser scale. Based on the pretreatment algorithm and some efficient algorithms, such as randomized method based on the semidefinite programming, branch and bound algorithm and complementary algorithm, we give three efficient algorithms for the binary quadratic programming.