borealis - A generalized global update algorithm for Boolean optimization problems

Abstract

Optimization problems with Boolean variables that fall into the nondeterministic polynomial (NP) class are of fundamental importance in computer science, mathematics, physics and industrial applications. Most notably, solving constraint-satisfaction problems, which are related to spin-glass-like Hamiltonians in physics, remains a difficult numerical task. As such, there has been great interest in designing efficient heuristics to solve these computationally difficult problems. Inspired by parallel tempering Monte Carlo in conjunction with the rejection-free isoenergetic cluster algorithm developed for Ising spin glasses, we present a generalized global update optimization heuristic that can be applied to different NP-complete problems with Boolean variables. The global cluster updates allow for a wide-spread sampling of phase space, thus considerably speeding up optimization. By carefully tuning the pseudo-temperature (needed to randomize the configurations) of the problem, we show that the method can efficiently tackle optimization problems with over-constraints or on topologies with a large site-percolation threshold. We illustrate the efficiency of the heuristic on paradigmatic optimization problems, such as the maximum satisfiability problem and the vertex cover problem.

arXiv comment19 pages, 7 figures, 1 table

References in corpus (13)

• Ising formulations of many NP problems
• Optimization with Extremal Dynamics
• A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• Strengths and Weaknesses of Parallel Tempering
• Robust Parameter Selection for Parallel Tempering
• Percolation thresholds on planar Euclidean relative neighborhood graphs
• Introduction to Monte Carlo Methods
• Site and bond percolation thresholds in $K_{n,n}$-based lattices: Vulnerability of quantum annealers to random qubit and coupler failures on chimera topologies

Cited by in corpus (7)

• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
• Adiabatic optimization versus diffusion Monte Carlo
• Effects of setting the temperatures in the parallel tempering Monte Carlo algorithm
• Patch-planting spin-glass solution for benchmarking
• Multi-Community Detection in Signed Graphs Using Quantum Hardware
• NAE-SAT-based probabilistic membership filters