  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.
