Summary Quadratic unconstrained binary optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. The main contribution of this article is to propose the bit duplication technique that can specify the number of duplicated bits, so that it can generate hard QUBO problem 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 bits is converted to a hard QUBO problem with bits . We use random QUBO problems, N‐Queen problems, traveling salesman problem and maximum weight matching problems for experiments. The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D‐Wave samplers with SA, D‐Wave hybrid and ABS2 QUBO solver are evaluated for solving these QUBO problems. The experimental results show that only a small scale of duplicated bits can make QUBO problems harder. Hence, the bit duplication technique is a potent method to generate hard QUBO problems and generated QUBO problems can be used as benchmark problems for evaluating the search performance of QUBO solvers.

Abstract An independent set of a graph is a subset of the nodes such that no two nodes in it are adjacent. The maximum independent set (MIS) problem is an optimization problem to find a largest independent set. The main contribution of this article is to introduce a generic iterative trial search algorithm that we call iMIS for finding approximate solutions for the MIS problem. The generic algorithm iMIS is designed so that it can be implemented to run on GPUs very efficiently. Since the performance of the algorithm varies depending on its search strategy, we present a hybrid algorithm that combines three strategies of the iMIS such that best one of them for an input graph is automatically selected. We have implemented our hybrid algorithm to run on a multi‐GPU server with eight NVIDIA A100 GPUs. And evaluated the performance for 66 DIMACS benchmark graphs and 78 random graphs with up to 256M nodes. We have also evaluated the performance of three previously published algorithms for the MIS problem and an approach using Gurobi linear programming solver. The experimental results show that our hybrid algorithm can find larger independent sets for all 144 graphs compared to other methods.

Abstract Quadratic unconstrained binary optimization (QUBO) is a combinatorial optimization problem. Since various NP‐hard problems such as the traveling salesman problem can be formulated as a QUBO instance, QUBO is used with a wide range of applications. The main contribution of this article is to propose high‐throughput FPGA implementations for the QUBO solver. We perform the local search using different bit‐selection strategies based on the simulated annealing in the proposed implementation. The hardware is a pipeline structure with no pipeline hazards using multiple instances, where the bit‐flip operation is always performed every clock cycle. We implemented the proposed circuit on Xilinx UltraScale+ FPGA VU9P. The implementation result shows that the circuit can search solutions per second. Besides, by sharing the block RAM that stores a weight matrix, we implemented a dual annealer architecture that has two QUBO solvers into the FPGA. As a result, the dual annealer architecture can search solutions per second.

The quadratic unconstrained binary optimization (QUBO) is recently gathering attention in conjunction with quantum annealing (QA), since it is equivalent to finding the ground state of an Ising model. Due to the limitation of current QA systems, classical computers may outperform them. Researchers have thus been proposed to solve QUBO on FPGAs, GPUs, and special purpose processors. In this paper, we propose an adaptive bulk search (ABS), a framework for solving QUBO that can perform many searches in parallel on multiple GPUs. It supports fully-connected Ising models with up to 32k spins and 16-bit weights. In our ABS, a CPU host performs genetic algorithm (GA) while GPUs asynchronously perform local searches. A bottleneck for solving QUBO exists in the evaluation of the energy function, which requires computational cost for each solution. We show this can be reduced to in our ABS. The experimental results show that, with four NVIDIA GeForce RTX 2080 Ti GPUs, our framework can search up to 1.24 × 1012 solutions per second. We also show that our system quickly solves maximum cut and traveling salesman problems.

Network coding is expected to improve throughput performance of multihop wireless networks. However, the throughput performance is significantly affected by the coding overhead at intermediate nodes. In this paper, we consider the trade-off between the throughput and coding overhead. Focusing on an intermediate node of a three-node chain topology, we model it as a single-server queueing system with two buffers. The per-flow throughput is analyzed with a continuous-time Markov chain, and the analysis is validated by simulation. Numerical results show that the analytical results agree fairly well with simulation when the offered loads of the flows are the same. It is also shown that a long processing time for coding causes a significant reduction in throughput.