Abstract
We define a new heuristic that guides the application of cycle resolution (CR) in MaxSAT, and show that it produces better lower bounds than those obtained by applying CR exhaustively as in Max-DPLL, and by applying CR in a limited way when unit propagation detects a contradiction as in MaxSatz.
This research was funded by MEC research projects TIN2006-15662-C02-02, TIN2007-68005-C04-04, and CONSOLIDER CSD2007-0022, INGENIO 2010.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Li, C.M., Manyà, F., Planes, J.: Exploiting unit propagation to compute lower bounds in branch and bound Max-SAT solvers. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 403–414. Springer, Heidelberg (2005)
Li, C.M., Manyà, F., Planes, J.: Detecting disjoint inconsistent subformulas for computing lower bounds for Max-SAT. In: Proceedings AAAI 2006, pp. 86–91 (2006)
Larrosa, J., Heras, F., de Givry, S.: A logical approach to efficient Max-SAT solving. Artificial Intelligence 172(2–3), 204–233 (2008)
Li, C.M., Manyà, F., Planes, J.: New inference rules for Max-SAT. Journal of Artificial Intelligence Research 30, 321–359 (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, C.M., Manyà, F., Mohamedou, N.O., Planes, J. (2008). Transforming Inconsistent Subformulas in MaxSAT Lower Bound Computation. In: Stuckey, P.J. (eds) Principles and Practice of Constraint Programming. CP 2008. Lecture Notes in Computer Science, vol 5202. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85958-1_46
Download citation
DOI: https://doi.org/10.1007/978-3-540-85958-1_46
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85957-4
Online ISBN: 978-3-540-85958-1
eBook Packages: Computer ScienceComputer Science (R0)