Improved Branch and Bound Algorithms for Max-2-SAT and Weighted Max-2-SAT
Issue date
2003Suggested citation
Planes Cid, Jordi;
.
(2003)
.
Improved Branch and Bound Algorithms for Max-2-SAT and Weighted Max-2-SAT.
Lecture Notes in Computer Science, 2003, vol. 2833, p. 991.
https://doi.org/10.1007/978-3-540-45193-8_115.
citations in Web of Science
citations in Scopus
Google Scholar
Abstract
We developed novel branch and bound algorithms for solving Max-SAT and weighted Max-SAT, which are variants of the algorithm of Borchers & Furman (BFA) [1]. We improved BFA by (i) defining a lower bound of better quality, and (ii) incorporating a new variable selection heuristic.