A fast global algorithm for singly linearly constrained separable binary quadratic program with partially identical parameters.

The singly linearly constrained separable binary quadratic programming problem (SLSBQP) has a wide variety of applications in practice. In real-life applications, the coefficients in the objective function and constraints generally appear with symmetric structure. In this paper, we propose an extremely efficient global optimization algorithm for solving SLSBQP with symmetric structure. We first develop a reformulation of SLSBQP based on an aggregate function defined on the symmetric structure in the problem, and derive the convex envelop function for the aggregate function. A branch-and-bound algorithm is then proposed to find the global solution of the reformulation of SLSBQP. Computational experiments show that the proposed algorithm is able to solve test instances with thousands of variables in less than 0.04 seconds on average, whereas the current state-of-the-art algorithms may fail to solve the same test instances in 200 seconds. The superior performance of the proposed algorithm clearly indicates the potential of the proposed algorithm in real-life applications. [ABSTRACT FROM AUTHOR]