Optimization via rejection-free partial neighbor search

DOI10.1007/S11222-023-10300-9MaRDI QIDQ6085191zbMATH OpenFDO

Authors Sigeng Chen, Jeffrey S. Rosenthal, Aki Dote, Hirotaka Tamura, Ali Sheikholeslami

Publication date 7 November 2023

Published in Statistics and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.02083

zbMATH Keywords

partial neighbor searchQUBOrejection-freesimulated annealing

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: Simulated Annealing using Metropolis steps at decreasing temperatures is widely used to solve complex combinatorial optimization problems. In order to improve its efficiency, we can use the Rejection-Free version of the Metropolis algorithm, which avoids the inefficiency of rejections by considering all the neighbors at every step. As a solution to avoid the algorithm from becoming stuck in local extreme areas, we propose an enhanced version of Rejection-Free called Partial Neighbor Search (PNS), which only considers random parts of the neighbors while applying Rejection-Free. We demonstrate the superior performance of the Rejection-Free PNS algorithm by applying these methods to several examples, such as the QUBO question, the Knapsack problem, the 3R3XOR problem, and the quadratic programming.

Recommendations

• scientific article; zbMATH DE number 4085427
• PARALLEL TEMPERING FOR THE TRAVELING SALESMAN PROBLEM
• Statistical mechanics: a general approach to combinatorial optimization
• An improved noise quantum annealing method for TSP
• scientific article; zbMATH DE number 1389083

Cites work

• A survey on metaheuristics for stochastic combinatorial optimization
• A vanilla Rao-Blackwellization of Metropolis-Hastings algorithms
• Computationally Related Problems
• Equation of state calculations by fast computing machines
• scientific article; zbMATH DE number 176065 (Why is no real title available?)
• Jump Markov chains and rejection-free Metropolis algorithms
• Neural networks and physical systems with emergent collective computational abilities
• Non-reversible Metropolis-Hastings
• On the History of Combinatorial Optimization (Till 1960)
• Optimization by simulated annealing
• Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
• Tabu Search—Part I
• Tabu Search—Part II
• The knapsack problem: A survey
• The unconstrained binary quadratic programming problem: a survey

Cited in

(3)

• Across neighborhood search for numerical optimization
• Optimization of partial search
• Sampling via Rejection-Free Partial Neighbor Search

This page was built for publication: Optimization via rejection-free partial neighbor search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6085191)