borealis -- a generalized global update algorithm for Boolean optimization problems

DOI10.1007/S11590-020-01570-7MaRDI QIDQ2228416zbMATH OpenOpenAlexFDO

Authors Zheng Zhu, Chao Fang, Helmut G. Katzgraber

Publication date 17 February 2021

Published in Optimization Letters (Search for Journal in Brave)

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

zbMATH Keywords

cluster algorithmMonte Carlooptimizationsatisfiabilityvertex cover

Mathematics Subject Classification ID

Boolean programming (90C09) Approximation methods and heuristics in mathematical programming (90C59)

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.

Recommendations

• A heuristic for Boolean optimization problems
• Boolean optimization algorithm on (0,1)-matrices
• scientific article; zbMATH DE number 3874955
• New heuristics and adaptive memory procedures for Boolean optimization problems
• Satisfiability-based algorithms for Boolean optimization

Cites work

• Approximation algorithms for combinatorial problems
• Beitrag zur Theorie des Ferromagnetismus
• CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
• Experimental analysis of approximation algorithms for the vertex cover and set covering problems
• Feedback-optimized parallel tempering Monte Carlo
• Going after the k-SAT threshold
• scientific article; zbMATH DE number 1082106 (Why is no real title available?)
• scientific article; zbMATH DE number 956863 (Why is no real title available?)
• Model checking with Boolean Satisfiability
• New Optimization Algorithms in Physics
• NuMVC: an efficient local search algorithm for minimum vertex cover
• On Solving the Partial MAX-SAT Problem
• On the Structure of Polynomial Time Reducibility
• Optimization by simulated annealing
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Random graphs.
• Robust parameter selection for parallel tempering
• Satisfiability-based set membership filters
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• The complexity of theorem-proving procedures
• Theory and Applications of Satisfiability Testing

Cited in

(1)

• Mathematical aspects of the Digital Annealer's simulated annealing algorithm

Describes a project that uses

Uses Software

• NuMVC
• Walksat
• CCLS

This page was built for publication: \(\boldsymbol{borealis}\) -- a generalized global update algorithm for Boolean optimization problems

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