Loading...
Please wait, while we are loading the content...
Similar Documents
Solving MAX-SAT and weighted MAX-SAT problems using branch-and-cut
| Content Provider | Semantic Scholar |
|---|---|
| Author | Joy, Steve Mitchell, John E. Borchers, Brian |
| Copyright Year | 1998 |
| Abstract | We describe a branch and cut algorithm for both MAX-SAT and weighted MAX-SAT. This algorithm uses the GSAT procedure as a primal heuristic. At each node we solve a linear programming (LP) relaxation of the problem. Two styles of separating cuts are added: resolution cuts and odd cycle inequalities. We compare our algorithm to an extension of the Davis Putnam Loveland (EDPL) algorithm and a Semi-De nite Programming (SDP) approach. Our algorithm is more e ective than EDPL on some problems, notably MAX-2-SAT. EDPL and SDP are more e ective on some other classes of problems. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://homepages.rpi.edu/~mitchj/papers/jco.pdf |
| Alternate Webpage(s) | http://eaton.math.rpi.edu/faculty/Mitchell/papers/jco.pdf |
| Alternate Webpage(s) | http://www.rpi.edu/~mitchj/papers/jco.pdf |
| Alternate Webpage(s) | http://www.rensselaer.edu/~mitchj/papers/jco.pdf |
| Alternate Webpage(s) | http://www.rpi.edu/~mitchj/papers/jco.ps |
| Alternate Webpage(s) | http://www.nmt.edu/~borchers/jmb.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
