logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

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

delete2025-05-23
delete0
PRE
AI
D
Donghao Liu
W
Wei Yang
H
H Wang
Y
Yu Du
Y
Yang Wang
Z
Zhipeng Lü
J
Jin‐Kao Hao
DOI：10.1016/j.cor.2025.107137delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
In recent years, quantum computing has driven significant excitement and innovation, with the Quadratic Unconstrained Binary Optimization (QUBO) model at its core. This paper introduces SATPR, a new open-source quantum-inspired metaheuristic algorithm that combines scatter search, adaptive tenure tabu search, and path-relinking. The adaptive nature of the tabu tenure, achieved through the integration of various heuristic components, enables SATPR to effectively solve different types of QUBO problem instances. Additionally, SATPR utilizes parallelism to fully leverage multi-threading capabilities, further enhancing its computational efficiency. We conducted extensive evaluations on large and challenging problem instances from four benchmark sets, including well-known QUBO and Max-Cut instances, as well as less explored random graph structures. Our results demonstrate that SATPR is highly competitive in both solution quality and computational efficiency when compared with leading metaheuristic QUBO solvers and the quantum-inspired Fixstars Amplify Annealing Engine.

Journal

C
Computers and Operations Research
IF:
4.3
Papers:
6.5K
Citations:
1.8W

Organization

No organization information available