QUBO問題の複雑さに関する研究
XIAOTIAN, LI · Institutional Repositories DataBase (IRDB)
Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization problem defined by an energy function that consists of a quadratic formula involving multiple binary variables.The goal of the QUBO problem is to find an optimal assignment of values to the variables that minimizes the energy function.With the increasing applicability of QUBO problems, QUBO solvers on different computing platforms have been developed.It is necessary to generate hard QUBO instances for improving and evaluating the performance of QUBO solvers.In this dissertation, we research in generating hard QUBO instances.First, we propose an effective method called bit duplication technique for generating hard QUBO instances with adjustable sizes.The idea is to duplicate specified number of bits and then to give constraints so that the corresponding two bits take the same binary values.By this technique, any QUBO problem with n bits is converted to a hard QUBO problem with (n + m) bits (0 < m ≤ n).Second, in order to avoid the increase in the original size after performing bit duplication technique, we propose a novel technique which we call bit reduction to reduce the size of the original QUBO problem before preforming bit duplication technique.Through this method, hard QUBO instances can be generated without increasing the size of the original QUBO problem.By combining the bit duplication and bit reduction technique, we propose the method for generating hard instance of QUBO problems from any original QUBO problem without changing the size. 1 We use random QUBO problems, N-Queens problems, Traveling Salesman Problem (TSP), maximum weight matching (MWM) problems and Satisfiability problems (SAT) as original QUBO problems to generate hard QUBO instances.The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D-Wave Hybrid and ABS2 QUBO solvers are evaluated for solving the generated hard QUBO instances.The experimental results show that generated QUBO instances are much hard for solving.