| Popis: |
The Quadratic Unconstrained Binary Optimization problem (QUBO) is an NP-hard optimization problem. QUBO can be reduced from many other combinatorial optimization problems. Hence, if we can solve QUBO, we can also solve many other problems. The paper proposes a novel method to solve QUBO by reducing it into the Bi-objective Bound-constrained Continuous Optimization problem (BBCO) and then solving the BBCO with Multi-Objective Particle Swarm Optimization (MOPSO). Using 45 benchmark problem instances, the paper also shows that a GPU parallel implementation of the proposed method on the CUDA architecture finds solutions with low relative errors for the benchmark instances at most 100 variables (76% of the benchmark instances) and runs up to 202 times faster than the corresponding multi-threaded CPU program on four physical cores. |
