Improved Branch and Bound Algorithms for Max-2-SAT and Weighted Max-2-SAT

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.

This Research was partially supported by the project CICYT TIC2001-1577 -C03-03 funded by the Spanish Ministerio de Ciencia y Tecnolog´ıa