Approximation Algorithms for MAXSAT
Well, this can be formulated as the problem of finding the ground state of an Ising-like Hamiltonian with 3-local terms. These don't occur naturally, but you would expect them to cool similarly to other systems, so simulated annealing should work just fine for the weighted version.