An External Definition of the One-Hot Constraint and Fast QUBO Generation for High-Performance Combinatorial Clustering

Abstract

Recently, a clustering method using a combinatorial optimization problem, called combinatorial clustering, has been drawing attention due to the rapid spreads of quantum annealing and simulated annealing. Combinatorial clustering is performed by minimizing an objective function under a condition to satisfy a one-hot constraint. The objective function and the constraint function are generally formulated to a unified objective function of a QUBO (Quadratic Unconstrained Binary Optimization) problem using the method of the Lagrange multiplier. The coefficients of the QUBO function can be represented by a square matrix, which is called the QUBO matrix.

Although the Lagrange multiplier needs to be large enough to avoid violating the constraint, it is usually hard to be set appropriately due to the limitation of the bit precision. For example, the latest quantum annealer can handle values represented by only six or fewer bits. Even conventional computing systems cannot control the larger value of the Lagrange multiplier as the number of data points increases. Besides, the execution time for combinatorial clustering increases exponentially as the problem size increases.
This is because the time for the QUBO matrix generation is long and a dominant factor of the total execution time when the problem size is large.

To solve these problems, this paper proposes combinatorial clustering that overcomes the limitation of the method of the Lagrange multiplier. The proposed method uses a QUBO solver that can externally define the one-hot constraint independent from the objective function, and the externally-defined constraint is satisfied by the operations with multiple bit-flips. As the QUBO function contains only the objective function, the method of the Lagrange multiplier is not necessary. The proposed method can optimize the objective function sufficiently even when the problem size is large. Since the constraint function is not included in the QUBO function, the proposed method also reduces the time for the QUBO matrix generation.

The experimental results obtained using the artificial and real data show that the proposed method can improve the quality of annealing-based clustering results in all data sets. The experimental results also clarify that the quality of the proposed method is almost equal to or better than that of quasi-optimal clustering methods such as K-means. The evaluation using the multiple traveling salesman problem shows that the proposed method can obtain shorter tour lengths than the conventional annealing-based clustering in all 13 cases and K-means++ in 6 out of 12 cases with a significant difference. Furthermore, the proposed method can accelerate the execution time for combinatorial clustering because there is no need to calculate the coefficients of the constraint function.