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.