<p>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 <a href="http://en.wikipedia.org/wiki/Simulated_annealing">simulated annealing</a> should work just fine for the weighted version.</p>

CC BY-SA 2.5
2010-11-23T09:19:51.210Z
Joe, after thinking about this I can't see how simulated annealing is different from MAX-WalkSAT. Isn't MAX-WalkSAT just a form of simulated annealing applied to this particular problem?
Huck Bennett
CC BY-SA 2.5
2010-11-24T11:21:06.780Z
@Huck: It depends on how you choose which variables to flip.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-09T15:58:48.420Z
2010-10-09T15:58:48.420Z
Joe Fitzsimons
<p>I think one can do reduction by simply duplicating the formulas according to their weight and therefore upper and lower bound results for unweighted 3-SAT also apply to weighted versions, with arbitrarily small lost. And according to a classical result of Johan Håstad, it is NP-hard to approximate 3-SAT beyond 7/8, which is the performance of assigning random values.</p>

<p>I am not sure about the performance of algorithms used in practical.</p>

CC BY-SA 3.0
2013-05-02T03:51:51.783Z
surely all *lower bounds* (hardness results) for unweighted 3-SAT apply also to weighted 3-SAT (which subsumes unweighted 3-SAT).
Neal Young
CC BY-SA 2.5
2010-10-09T06:39:52.530Z
That reduction is not polynomial in the length of the weight. If you give me a weight of length O(n) then I'll have to make 2^(O(n)) copies of the clause.
Huck Bennett
CC BY-SA 2.5
2010-10-09T06:45:24.843Z
Furthermore, if I restricted the problem to MAX-SAT with non-repeating clauses (still NP-hard) that would not work.
Huck Bennett
CC BY-SA 2.5
2010-10-09T06:20:16.783Z
2010-10-09T06:20:16.783Z
sangxia
<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-09T14:43:11.687Z
This is not really on topic as it is asking about heuristics and implementation experience rather than provable algorithms.
Warren Schudy
CC BY-SA 2.5
2010-10-09T16:21:44.210Z
Algorithms which appear strong in practice but about which we haven't yet proven anything aren't theoretical enough? I'd be very interested to hear about any provably "good" algorithms, but I don't think there are too many.
Huck Bennett
CC BY-SA 2.5
2010-10-10T00:43:27.860Z
@Warren: I think perhaps that is taking things a little too far. The question basically amounts to "What algorithms are good for WEIGHTED-MAX-SAT?" which is a perfectly reasonable question to ask. Many SAT solvers rely on heuristics too. Even though their worst case performance is poor, they do surprisingly well. If every question related to only exactly proved complexity results, I doubt the site would be very popular. After all, we already have the zoo.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-10T08:07:49.513Z
You mean, the zoo [1]? 

[1] http://qwiki.stanford.edu/wiki/Complexity_Zoo
gphilip
CC BY-SA 2.5
2010-10-11T17:35:47.530Z
The MAXSAT competition has divisions for weighted and for unweighted: http://www.maxsat.udl.cat/10/results/
Radu GRIGore
CC BY-SA 2.5
2010-10-11T17:38:38.487Z
Here's one readable description of one of the algorithms used: http://scholar.google.com/scholar?cluster=14077294269217865108
Radu GRIGore
CC BY-SA 2.5
2010-10-20T14:16:08.820Z
@Warren: In the '80s and '90s, at many universities, theoretical computer science was very unpopular and looked down upon by the rest of computer science because it was viewed as unconnected to practice. Eventually, Google and other successes convinced them that we were worth talking to. Let's please not close off the lines of communication from the other side now, after having worked so long to open them. That would be very bad for the field, not to mention the TCS job market.
Peter Shor 
CC BY-SA 2.5
2010-10-20T17:38:13.787Z
@Peter: let's move this discussion to meta: http://meta.cstheory.stackexchange.com/questions/120/are-applied-questions-off-topic/ .
Warren Schudy
<ds.algorithms><approximation-algorithms><sat><approximation-hardness>
Approximation Algorithms for MAXSAT
Huck Bennett
# Approximation Algorithms for MAXSAT

(Asked by: username_0 on 2010-10-09)

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.

**Tags:** ds.algorithms, approximation-algorithms, sat, approximation-hardness
> **Comments:**
> **username_1**: This is not really on topic as it is asking about heuristics and implementation experience rather than provable algorithms.  
> **username_0**: Algorithms which appear strong in practice but about which we haven't yet proven anything aren't theoretical enough? I'd be very interested to hear about any provably "good" algorithms, but I don't think there are too many.  
> **username_2**: @Warren: I think perhaps that is taking things a little too far. The question basically amounts to "What algorithms are good for WEIGHTED-MAX-SAT?" which is a perfectly reasonable question to ask. Many SAT solvers rely on heuristics too. Even though their worst case performance is poor, they do surprisingly well. If every question related to only exactly proved complexity results, I doubt the site would be very popular. After all, we already have the zoo.  
> **username_3**: You mean, the zoo [1]?   [1] http://qwiki.stanford.edu/wiki/Complexity_Zoo  
> **username_4**: The MAXSAT competition has divisions for weighted and for unweighted: http://www.maxsat.udl.cat/10/results/  
> **username_4**: Here's one readable description of one of the algorithms used: http://scholar.google.com/scholar?cluster=14077294269217865108  
> **username_5**: @Warren: In the '80s and '90s, at many universities, theoretical computer science was very unpopular and looked down upon by the rest of computer science because it was viewed as unconnected to practice. Eventually, Google and other successes convinced them that we were worth talking to. Let's please not close off the lines of communication from the other side now, after having worked so long to open them. That would be very bad for the field, not to mention the TCS job market.  
> **username_1**: @Peter: let's move this discussion to meta: http://meta.cstheory.stackexchange.com/questions/120/are-applied-questions-off-topic/ .  

---

## 2 answers

### Answer by username_2 on 2010-10-09. Score: 5 | Accepted answer

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](http://en.wikipedia.org/wiki/Simulated_annealing) should work just fine for the weighted version.

> **Comments:**
> **username_0**: Joe, after thinking about this I can't see how simulated annealing is different from MAX-WalkSAT. Isn't MAX-WalkSAT just a form of simulated annealing applied to this particular problem?  
> **username_2**: @Huck: It depends on how you choose which variables to flip.  

---

### Answer by username_6 on 2010-10-09. Score: 4

I think one can do reduction by simply duplicating the formulas according to their weight and therefore upper and lower bound results for unweighted 3-SAT also apply to weighted versions, with arbitrarily small lost. And according to a classical result of Johan Håstad, it is NP-hard to approximate 3-SAT beyond 7/8, which is the performance of assigning random values.

I am not sure about the performance of algorithms used in practical.

> **Comments:**
> **username_0**: That reduction is not polynomial in the length of the weight. If you give me a weight of length O(n) then I'll have to make 2^(O(n)) copies of the clause.  
> **username_0**: Furthermore, if I restricted the problem to MAX-SAT with non-repeating clauses (still NP-hard) that would not work.  
> **username_7**: surely all *lower bounds* (hardness results) for unweighted 3-SAT apply also to weighted 3-SAT (which subsumes unweighted 3-SAT).  

---

