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.
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 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.
Quadratic unconstrained binary optimization (QUBO) is a classic NP-hard problem with an enormous number of applications. Local search strategy (LSS) is one of the most fundamental algorithmic concepts and has been successfully applied to a wide range of hard combinatorial optimization problems. One LSS that has gained the attention of researchers is the r-flip (also known as r-Opt) strategy. Given a binary solution with n variables, the r-flip strategy “flips” r binary variables to obtain a new solution if the changes improve the objective function. The main purpose of this paper is to develop several results for the implementation of r-flip moves in QUBO, including a necessary and sufficient condition that when a 1-flip search reaches local optimality, the number of candidates for implementation of the r-flip moves can be reduced significantly. The results of the substantial computational experiments are reported to compare an r-flip strategy-embedded algorithm and a multiple start tabu search algorithm on a set of benchmark instances and three very-large-scale QUBO instances. The r-flip strategy implemented within the algorithm makes the algorithm very efficient, leading to very high-quality solutions within a short CPU time.
This technical report presents an empirical validation study of Branch-Collapse search for dense Quadratic Unconstrained Binary Optimization (QUBO). The method is evaluated against greedy local search, simulated annealing, and an implemented Tabu search baseline under fixed benchmark conditions. The study reports results on locked dense random QUBO instances, including primary benchmarks at n = 50, 60, and 70, larger scaling probes, and equal wall-clock Tabu comparisons at n = 300, n = 500, and n = 750. The strongest completed validation compares an RQCE-derived Branch-Collapse solver against the implemented Tabu baseline on n = 500 dense QUBO instances across five Python hash seeds, achieving 100 wins, 0 losses, and 0 ties at 0.5s, 1.0s, and 2.0s, and 98 wins, 2 losses, and 0 ties at 5.0s. A further n = 750 scaling pilot achieved 10 wins, 0 losses, and 0 ties at each tested budget. The report includes baseline descriptions, benchmark methodology, robustness checks, selected seed-level energy tables, checkpoint audit outputs, file-hash evidence for a locked validation artifact, and a clear statement of limitations. The results should be interpreted as author-reported empirical validation under the stated benchmark conditions, not as a claim of global optimality or superiority over all possible Tabu implementations or all QUBO instance families. A separate controlled technical appendix containing additional seed-level outputs, validation commands, audit records, and locked-file metadata is retained by the author and may be made available for controlled technical review.
Quadratic Unconstrained Binary Optimization (QUBO) is a central formulation for combinatorial optimization and has gained increasing attention due to its compatibility with quantum, hybrid quantum-classical, and quantum-inspired solvers. However, translating natural-language problem descriptions into correct QUBO formulations remains difficult, requiring the identification of binary variables, constraints, objective functions, penalty terms, and suitable penalty weights. This process is time-consuming and often demands substantial domain expertise. To address this challenge, we propose an end-to-end multi-agent framework that automatically generates QUBO formulations from natural-language problem descriptions, supported by structured or unstructured test cases. To evaluate its performance, We also introduce QUBOBench, a benchmark containing 100 combinatorial optimization problems across 12 application domains, curated from peer-reviewed literature, competitions, and canonical NP-hard problems. Experimental results show that our framework achieves 68% accuracy on QUBOBench, outperforming a direct single-call baseline by 22%. Further analysis identifies iterative self-repair as the most important component contributing to improved performance. The data and code are open-sourced at https://quitttcat.github.io/QuantumQUBOAgent.
We provide a method for efficiently evaluating two-flip moves that simultaneously change the values of two 0-1 variables in search methods for binary unconstrained quadratic optimisation problems (UQP). We extend a framework recently proposed by the authors for creating efficient evaluations of one-flip moves to yield a method requiring significantly less computation time than a direct sequential application of one-flips. A tabu search algorithm that combines one-flip and two-flip moves, in a study currently in process, has made use of this extension to produce very competitive results on some UQP benchmark instances.