Data structures for speeding up Tabu Search when solving sparse quadratic unconstrained binary optimization problems

The quadratic unconstrained binary optimization (QUBO) problem belongs to the NP-hard complexity class of problems and has been the subject of intense research since the 1960s. Many problems in various areas of research can be reformulated as QUBO problems, and several reformulated instances have sparse matrices. Thus, speeding up implementations of methods for solving the QUBO problem can benefit all of those problems. Among such methods, Tabu Search (TS) has been particularly successful. In this work, we propose data structures to speed up TS implementations when the instance matrix is sparse. Our main result consists in employing a compressed sparse row representation of the instance matrix, and priority queues for conducting the search over the solution space. While our literature review indicates that current TS procedures for QUBO take linear time on the number of variables to execute one iteration, our proposed structures may allow better time complexities than that, depending on the sparsity of the instance matrix. We show, by means of extensive computational experiments, that our techniques can significantly decrease the processing time of TS implementations, when solving QUBO problem instances with matrices of relatively high sparsity. To assess the quality of our results regarding more intricate procedures, we also experimented with a Path Relinking metaheuristic implemented with the TS using our techniques. This experiment showed that our techniques can allow such metaheuristics to become more competitive.