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

Ricardo N. Liang (), Eduardo A. J. Anacleto () and Cláudio N. Meneses ()
Additional contact information
Ricardo N. Liang: Federal University of ABC
Eduardo A. J. Anacleto: Federal University of ABC
Cláudio N. Meneses: Federal University of ABC

Journal of Heuristics, 2022, vol. 28, issue 4, No 2, 433-479

Abstract: Abstract 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.

Keywords: Zero-one optimization; Tabu Search; Sparsity; Priority queues; Computational efficiency (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-022-09498-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:28:y:2022:i:4:d:10.1007_s10732-022-09498-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-022-09498-0

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().