Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Heuristics

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

Ricardo N. Liang, Eduardo A.J. Anacleto, Cláudio N. Meneses

Published Apr 27, 2022• 4 citations
Publisher
DOI
10.1007/s10732-022-09498-0

Related papers

Multistart Tabu Search Strategies for the Unconstrained Binary Quadratic Optimization Problem

Gintaras Palubeckis

Annals of Operations Research•Aug 27, 2004•155 citations

Enhanced open-source scatter search algorithm for solving quadratic unconstrained binary optimization problems

Donghao Liu, Wei Yang, H Wang +4 more

Computers & Operations Research•May 23, 2025•4 citations

Automated Tabu Tenure Tuning by Trajectory Metrics for Quadratic Unconstrained Binary Optimization

Masahiko Sugimura, Keiichiro Yamamura, Hiroki Ishikura +4 more

Abstract Tabu Search is a promising approach for solving quadratic unconstrained binary optimization (QUBO) problems. A key parameter in Tabu Search is tabu tenure, which governs the balance between intensification and diversification in the search process. In this work, we aim to develop a systematic method for determining the effective tabu tenure tailored to each QUBO instance, thereby enhancing overall solver performance. To achieve this, we focus on the statistics obtained during the search, which we term “trajectory metrics.” We consolidate existing trajectory metrics from the literature with newly proposed ones and analyze their responses to variations in tabu tenure using three criteria: suitability for tuning, noise robustness, and classification potential. Based on this analysis, we introduce a method for determining the effective tabu tenure and evaluate its performance across several problem instances. Experimental results demonstrate that the proposed approach improves solving performance compared to a well-known standard Tabu Search-based method.

Journal of Heuristics•Dec 27, 2025•0 citations

The Quadratic Unconstrained Binary Optimization Problem: Theory, Algorithms, and Applications

Springer eBooks•Jan 1, 2022•83 citations

A3TUM: Automated Tabu Tenure Tuning by Unique Move for Quadratic Unconstrained Binary Optimization

Masahiko Sugimura, Matthieu Parizy

Tabu search is one of the promising solving methods for quadratic unconstrained binary problem (QUBO). A critical parameter of tabu search is tabu tenure, which balances the behavior of the solver between greedy and exploratory. Our goal is to establish a way to find out tabu tenure suitable for each problem instance in QUBO formulation and utilize it to enhance solver performance. In order to achieve the goal, we proposed a new metric unique move, which is a number of unique decision variables changed, and studied its behavior in several problem instances in QUBO formulation. Based on the study, our proposed method named A3TUM was designed to take a suitable sub-method for each problem instance by classifying problems into typical patterns based on the behavior of unique move. Experimental result shows the effectiveness of the method both in estimation accuracy of tabu tenure and in solving performance compared to a robust tabu search based method as a baseline.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2024•2 citations

Efficient evaluations for solving large 0-1 unconstrained quadratic optimisation problems

Fred Glover, Jin‐Kao Hao

Abstract: We provide a method for efficiently evaluating moves that complement values of 0–1 variables in search methods for binary unconstrained quadratic optimisation problems. Our method exploits a compact matrix representation and offers further improvements in speed by exploiting sparse matrices that arise in large-scale applications. The resulting approach, which works with integer or real data, can be applied to improve the efficiency of a variety of different search processes, especially in the case of commonly encountered applications that involve large and sparse matrices. It also enables larger problems to be solved than could previously be handled within a given amount of available memory. Our evaluation method has been embedded in a tabu search algorithm in a sequel to this paper, yielding a method that efficiently matches or improves currently best-known results for instances from widely used benchmark sets having up to 7,000 variables.

International Journal of Metaheuristics•Jan 1, 2010•45 citations
Abstract Tabu Search is a promising approach for solving quadratic unconstrained binary optimization (QUBO) problems. A key parameter in Tabu Search is tabu tenure, which governs the balance between intensification and diversification in the search process. In this work, we aim to develop a systematic method for determining the effective tabu tenure tailored to each QUBO instance, thereby enhancing overall solver performance. To achieve this, we focus on the statistics obtained during the search, which we term “trajectory metrics.” We consolidate existing trajectory metrics from the literature with newly proposed ones and analyze their responses to variations in tabu tenure using three criteria: suitability for tuning, noise robustness, and classification potential. Based on this analysis, we introduce a method for determining the effective tabu tenure and evaluate its performance across several problem instances. Experimental results demonstrate that the proposed approach improves solving performance compared to a well-known standard Tabu Search-based method.
Tabu search is one of the promising solving methods for quadratic unconstrained binary problem (QUBO). A critical parameter of tabu search is tabu tenure, which balances the behavior of the solver between greedy and exploratory. Our goal is to establish a way to find out tabu tenure suitable for each problem instance in QUBO formulation and utilize it to enhance solver performance. In order to achieve the goal, we proposed a new metric unique move, which is a number of unique decision variables changed, and studied its behavior in several problem instances in QUBO formulation. Based on the study, our proposed method named A3TUM was designed to take a suitable sub-method for each problem instance by classifying problems into typical patterns based on the behavior of unique move. Experimental result shows the effectiveness of the method both in estimation accuracy of tabu tenure and in solving performance compared to a robust tabu search based method as a baseline.
Abstract: We provide a method for efficiently evaluating moves that complement values of 0–1 variables in search methods for binary unconstrained quadratic optimisation problems. Our method exploits a compact matrix representation and offers further improvements in speed by exploiting sparse matrices that arise in large-scale applications. The resulting approach, which works with integer or real data, can be applied to improve the efficiency of a variety of different search processes, especially in the case of commonly encountered applications that involve large and sparse matrices. It also enables larger problems to be solved than could previously be handled within a given amount of available memory. Our evaluation method has been embedded in a tabu search algorithm in a sequel to this paper, yielding a method that efficiently matches or improves currently best-known results for instances from widely used benchmark sets having up to 7,000 variables.