Polynomial time solvable algorithm to linearly constrained binary quadratic programming problems with Q being a five-diagonal matrix

摘要

Binary quadratic programming (BQP) is a typical integer programming problem widely applied in the field of signal processing, economy, management and engineering. However, it's NP-hard and lacks efficient algorithms. Due to this reason, in this paper, a novel polynomial algorithm to linearly constrained binary quadratic programming problems with Q being a five-diagonal matrix is focused by combining the basic algorithm proposed in [1], [2], [3] and the dynamic programming method. We first briefly deduce the basic algorithm. Then, the algorithm is proposed to solve this special problem. In addition, a specific example is presented to illustrate the new algorithm. Lastly, we demonstrate its polynomial feature as well as its high efficiency.