Approximation Algorithms for MAXSAT Trying to find the optimal solution to WEIGHTED-MAX-3SAT, the weighted version of the 3-SAT optimization problem, is NP-hard. In fact, even approximating the non-weighted version of MAX-SAT arbitrarily well is provably NP-hard by the PCP Theorem.

A canonical algorithm for approximating WEIGHTED-MAX-3SAT is MAX-WalkSAT. Looking around I found some information on other algorithms (i.e. branch-and-bound, the DPL algorithm) which are commonly used to find solutions to 3-SAT or (unweighted) MAX-3SAT, but I didn't see any discussion of how well these would work for the weighted version. Intuitively, without being adapted they would not work as well.

I'm wondering what other algorithms are commonly used to approximate WEIGHTED-MAX-SAT, if there are well-known WEIGHTED-MAX-SAT solvers, and the relative quality of these algorithms/solvers.
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.