Solving unconstrained binary quadratic programming using binary particle swarm optimization

The unconstrained binary quadratic programming is known to be NP-hard, and is a unified model for a lot of combinatorial optimization problems. This paper presents a binary particle swarm optimization for solving the unconstrained binary quadratic programming. The proposed algorithm adopts a method to update position, and uses mutation operation to produce new solutions. Then, the new solutions are refined by a local search procedure. The algorithm was tested on a benchmark set from the literature. The experimental results show that the proposed algorithm is able to find high-quality solutions within an acceptable runtime.