Polynomial time solvable algorithms to a class of unconstrained and linearly constrained binary quadratic programming problems

Binary quadratic programming (BQP) is a typical integer programming problem widely applied in the field of signal processing, economy, management and engineering. However, it is NP-hard and lacks efficient algorithms. Due to this reason, in this paper, some novel polynomial algorithms are proposed to solve a class of unconstrained and linearly constrained binary quadratic programming problems. We first deduce the polynomial time solvable algorithms to the unconstrained binary quadratic programming problems with Q   being a seven-diagonal matrix (UBQP7)(UBQP7) and a five-diagonal matrix (UBQP5)(UBQP5) respectively with two different approaches. Then, the algorithm to unconstrained problem is combined with the dynamic programming method to solve the linearly constrained binary quadratic programming problem with Q   being a five-diagonal matrix (LCBQP5)(LCBQP5). In addition, the polynomial solvable feature of these algorithms is analyzed and some specific examples are presented to illustrate these new algorithms. Lastly, we demonstrate their polynomial feature as well as their high efficiency.