Combinatorial Optimization by Decomposition on Hybrid CPU–non-CPU Solver Architectures

By Ali Narimani, Seyed Saeed Rezaei, & Arman Zaribafiyan 
The advent of special-purpose hardware such as FPGA- or ASIC-based annealers and quantum processors has shown potential in solving certain families of complex combinatorial optimization problems more efficiently than conventional CPUs. We show that to address an industrial optimization problem, a hybrid architecture of CPUs and non-CPU devices is inevitable. In this paper, we propose problem decomposition as an effective method for designing a hybrid CPU–non-CPU optimization problem solver. We introduce the required algorithmic elements for making problem decomposition a viable approach in meeting real-world constraints such as communication time and the potential higher cost of using non-CPU hardware. We then turn to the well-known maximum clique problem, and propose a new decomposition method for this problem. Our method enables us to solve the maximum clique problem on very large graphs using non-CPU hardware that is considerably smaller in size than the graph. As an example, we demonstrate that the maximum clique problem on the com-Amazon graph, with 334,863 vertices and 925,872 edges, can be solved using a single problem embedding on fully connected hardware with at least 21 nodes, such as the D-Wave 2000Q. We also show that our proposed problem decomposition approach can improve the runtime of two of the best-known classical algorithms for large, sparse graphs, namely PMC and BBMCSP, by orders of magnitude. In the light of our study, we believe that even new non-CPU hardware that is small in size could become competitive with CPUs if it could be either mass produced and highly parallelized, or able to provide high-quality solutions to specific problems significantly faster than CPUs.
PDF    ARXIV PREPRINT

Most Recent Papers

Variationally Scheduled Quantum Simulation

By Shunji Matsuura, Samantha Buck, Valentin Senicourt, & Arman Zaribafiyan Eigenstate preparation is ubiquitous in quantum computing, and a standard approach for generating the lowest-energy states of a given system is by employing adiabatic state preparation...

A Quantum Annealing-Based Approach to Extreme Clustering

By Tim Jaschek, Marko Bucyk, & Jaspreet S. Oberoi Clustering, or grouping, dataset elements based on similarity can be used not only to classify a dataset into a few categories, but also to approximate it by a relatively large number of representative elements. In...