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.
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.
Ising machines have recently gained a significant attention as a promising approach to combinatorial optimization problems, which are notoriously challenging for conventional computers to solve efficiently. In contrast to conventional computers, Ising machines operate based on the principles of the Ising model derived from statistical mechanics. Ising machines tackle combinatorial optimization problems by transforming them into Quadratic Unconstrained Binary Optimization (QUBO) formulations. The Traveling Salesperson Problem (TSP) is a prominent example of such optimization challenges and is widely recognized for its computational difficulty on conventional computers. Although Ising machines offer the potential for efficiently solving TSPs, the process of a QUBO formulation, namely the generation of a QUBO matrix that represents a TSP, demands substantial memory resources and considerable computation overheads. This study proposes a compressed QUBO format for TSP. This format reduces the dimensionality of the QUBO matrix for TSP by leveraging repetitive values, structural patterns, and sparsity within the matrix. The proposed format enhances the efficiency of data preprocessing, significantly reducing both the computational time required for QUBO matrix generation and the associated memory usage. These improvements contribute to the practical applicability of digital hardware-based Ising machines for addressing large-scale combinatorial optimization problems, thereby expanding their utility in solving complex real-world challenges.
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.
When solving a combinatorial optimization problem with Ising machines, we have to formulate it onto an energy function of Ising model. Here, how to determine the penalty coefficients in the energy function is a great concern if it includes constraint terms. In this paper, we focus on a traveling salesman problem (TSP, in short), one of the combinatorial optimization problems with equality constraints. Firstly, we investigate the relationship between the penalty coefficient and the accuracy of solutions in a TSP. Based on it, we propose a method to obtain a TSP quasi-optimum solution, which is called multiple coefficients trial method. In our proposed method, we use an Ising machine to solve a TSP by changing a penalty coefficient every trial, the TSP solutions can converge very fast in total. Compared to naive methods using simulated-annealing-based Ising machines, we confirmed that our proposed method can reduce the total number of annealing iterations to 1/10 to 1/1000 to obtain a quasi-optimum solution in 32-city TSPs.
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.
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.