Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Journal of Networking and Computing

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

Masahito Kumagai, Kazuhiko Komatsu, Fumiyo Takano, Takuya Araki, Masayuki Sato, Hiroaki Kobayashi

Published Jan 1, 2021• 14 citations
Publisher

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.

DOI
10.15803/ijnc.11.2_463

Related papers

Combinatorial Clustering Based on an Externally-Defined One-Hot Constraint

Masahito Kumagai, Kazuhiko Komatsu, Fumiyo Takano +3 more

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 constraint. The objective function and the constraint function are generally formulated to a unified objective function of a QUBO (Quadratic Unconstrained Binary Optimization) problem by the method of the Lagrange multiplier.Although the Lagrange multiplier needs to be large enough to avoid violating the one-hot constraint, the Lagrange multiplier usually cannot be set appropriately due to the limitation of the bit precision. The latest quantum annealer can handle values represented by only six or fewer bits. Even conventional computing systems cannot handle the larger value of the Lagrange multiplier as the number of data points increases.To solve this problem, this paper proposes combinatorial clustering that overcomes the limitations 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 bit-flip operations. Since the constraint function is not included in the objective function, it is no longer needed to determine the Lagrange multiplier. The experimental results show that the proposed method can improve the quality of clustering results.

International Symposium on Computing and Networking•Nov 1, 2020•18 citations

A Constraint Partition Method for Combinatorial Optimization Problems

Makoto Onoda, Kazuhiko Komatsu, Masahito Kumagai +2 more

Ising machines have attracted much attention in recent years because of their potential in solving combinatorial optimization problems that are difficult to be solved using conventional computers. Ising machines solve the optimization problem that can be transformed into a quadratic unconstrained binary optimization (QUBO) problem. In the case of a problem with constraints, named a constraint problem, an objective function and constraint function with penalty coefficients are combined into a single Hamiltonian of a QUBO problem. When solving a constraint problem, the accuracy of the solution decreases compared to a QUBO problem with an objective function only. This is because penalty coefficients are set to excessively large values to prevent constraint violations. As a result, it becomes difficult to minimize the objective function. To solve this problem, this paper proposes a method that partitions constraint functions and reduces the value of the penalty coefficients. The performance evaluation using the traveling salesperson problem (TSP) with one-hot constraints demonstrates that the proposed method can improve the solution accuracy compared to the conventional method.

IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)•Dec 18, 2023•2 citations

Partitioning QUBO with two-way one-hot conditions on traveling salesman problems for city distributions with multiple clusters

Akihiro Yatabe

We introduce a method for solving a quadratic unconstrained binary optimization (QUBO) with the two-way one-hot constraints by dividing the QUBO into parts and solving it with an Ising machine. The one-hot constraint is a constraint condition in that only one binary variable takes the value one for a set of multiple binary variables. The two-way one-hot constraint imposes one-hot constraint conditions on every row and every column of a two-dimensional array of binary variables with equal numbers of rows and columns. For example, traveling salesman problems (TSPs) have two-way one-hot constraints. We propose two methods to solve a TSP by dividing the cities into clusters based on information in the QUBO matrix. The proposed methods decompose cities into clusters and solve TSPs for each cluster. We solve TSPs such that the cities are distributed in clusters and compare the results of the two proposed methods with the results of solving the problem without partitioning. The results show that the proposed methods are robust to the coefficient parameters in the Hamiltonian of QUBO and can obtain a solution closer to the optimal solution when solving the problem without partitioning is hard. We also discuss the application of the methods proposed in the TSPs to the quadratic assignment problems and to the problems of ordering things.

Frontiers in Computer Science•Apr 26, 2024•2 citations

Techniques to enhance a QUBO solver for permutation-based combinatorial optimization

Siong Thye Goh, Jianyuan Bo, Sabrish Gopalakrishnan +1 more

Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•10 citations

QUBO問題の複雑さに関する研究

LI XIAOTIAN

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.

•Mar 23, 2025•0 citations

Automaton-based methodology for implementing optimization constraints for quantum annealing

Hristo N. Djidjev

Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.

ACM International Conference on Computing Frontiers (CF)•May 11, 2020•4 citations
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.
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 constraint. The objective function and the constraint function are generally formulated to a unified objective function of a QUBO (Quadratic Unconstrained Binary Optimization) problem by the method of the Lagrange multiplier.Although the Lagrange multiplier needs to be large enough to avoid violating the one-hot constraint, the Lagrange multiplier usually cannot be set appropriately due to the limitation of the bit precision. The latest quantum annealer can handle values represented by only six or fewer bits. Even conventional computing systems cannot handle the larger value of the Lagrange multiplier as the number of data points increases.To solve this problem, this paper proposes combinatorial clustering that overcomes the limitations 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 bit-flip operations. Since the constraint function is not included in the objective function, it is no longer needed to determine the Lagrange multiplier. The experimental results show that the proposed method can improve the quality of clustering results.
Ising machines have attracted much attention in recent years because of their potential in solving combinatorial optimization problems that are difficult to be solved using conventional computers. Ising machines solve the optimization problem that can be transformed into a quadratic unconstrained binary optimization (QUBO) problem. In the case of a problem with constraints, named a constraint problem, an objective function and constraint function with penalty coefficients are combined into a single Hamiltonian of a QUBO problem. When solving a constraint problem, the accuracy of the solution decreases compared to a QUBO problem with an objective function only. This is because penalty coefficients are set to excessively large values to prevent constraint violations. As a result, it becomes difficult to minimize the objective function. To solve this problem, this paper proposes a method that partitions constraint functions and reduces the value of the penalty coefficients. The performance evaluation using the traveling salesperson problem (TSP) with one-hot constraints demonstrates that the proposed method can improve the solution accuracy compared to the conventional method.
We introduce a method for solving a quadratic unconstrained binary optimization (QUBO) with the two-way one-hot constraints by dividing the QUBO into parts and solving it with an Ising machine. The one-hot constraint is a constraint condition in that only one binary variable takes the value one for a set of multiple binary variables. The two-way one-hot constraint imposes one-hot constraint conditions on every row and every column of a two-dimensional array of binary variables with equal numbers of rows and columns. For example, traveling salesman problems (TSPs) have two-way one-hot constraints. We propose two methods to solve a TSP by dividing the cities into clusters based on information in the QUBO matrix. The proposed methods decompose cities into clusters and solve TSPs for each cluster. We solve TSPs such that the cities are distributed in clusters and compare the results of the two proposed methods with the results of solving the problem without partitioning. The results show that the proposed methods are robust to the coefficient parameters in the Hamiltonian of QUBO and can obtain a solution closer to the optimal solution when solving the problem without partitioning is hard. We also discuss the application of the methods proposed in the TSPs to the quadratic assignment problems and to the problems of ordering things.
Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.
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.
Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.