Proceedings

Minimum Satisfiability and Its Applications

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 605-609.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-108

© 2011 International Joint Conferences on Artificial Intelligence

Abstract

We define solving techniques for the Minimum Satisfiability Problem (MinSAT), propose an efficient branch-and-bound algorithm to solve the Weighted Partial MinSAT problem, and report on an empirical evaluation of the algorithm on Min-3SAT, MaxClique, and combinatorial auction problems. Techniques solving MinSAT are substantially different from those for the Maximum Satisfiability Problem (MaxSAT). Our results provide empirical evidence that solving combinatorial optimization problems by reducing them to MinSAT may be substantially faster than reducing them to MaxSAT, and even competitive with specific algorithms. We also use MinSAT to study an interesting correlation between the minimum number and the maximum number of satisfied clauses of a SAT instance.

  1. [Avidor and Zwick, 2005] Adi Avidor and Uri Zwick. Approxi- mating min 2-sat and min 3-sat. Theory of Computing Systems, 38(3):329-345, 2005.
  2. [Cooper et al., 2010] M. Cooper, S. de Givry, M. Sanchez, T. Schiex, M. Zytnicki, and T. Werner. Soft arc consistency revisited Artificial Intelligence, (7-8):449-478, 2010 [
  3. [Fujishima et al., 1999] Yuzo Fujishima, Kevin Leyton-Brown, and Yoav Shoham. Taming the computational complexity of combi- natorial auctions: Optimal and approximate approaches. In IJ- CAI, pages 548-553, 1999. IJCAI
  4. [Heras et al., 2008] Federico Heras, Javier Larrosa, Simon de Givry, and Thomas Schiex. 2006 and 2007 Max-SAT evaluations: Contributed instances. JSAT, 4(2-4):239-250, 2008.
  5. [Kohli et al., 1994] Rajeev Kohli, Ramesh Krishnamurti, and Prakash Mirchandani. The minimum satisfiability problem. SIAM J. Discrete Mathematics, 7(2):275-283, 1994.
  6. [Konc and Janezic, 2007] J. Konc and D. Janezic. An improved branch and bound algorithm for the maximum clique problem. Communications in Mathematical and in Computer Chemistry, 58:569-590, 2007.
  7. [Kuegel, 2010] Adrian Kuegel. Improved exact solver for the Weighted MAX-SAT problem. In Workshop Pragmatics of SAT, 2010.
  8. [Leyton-Brown et al., 2000] Kevin Leyton-Brown, Mark Pearson, and Yoav Shoham. Towards a universal test suite for combi- natorial auction algorithms. In ACM Conference on Electronic Commerce, pages 66-76, 2000.
  9. [Li and Anbulagan, 1997] Chu Min Li and Anbulagan, Heuristics Based on Unit Propagation for Satisfiability Problems. In Pro- ceedings of IJCAI, pages 366-371, [ IJCAI
  10. [Li and Manyà, 2009] Chu Min Li and F. Manyà. MaxSAT, hard and soft constraints. In Armin Biere, Hans van Maaren, and Toby Walsh, editors, Handbook of Satisfiability, pages 613-631. IOS Press, 2009.
  11. [Li and Quan, 2010a] Chu Min Li and Zhe Quan. Combining graph structure exploitation and propositional reasoning for the maxi- mum clique problem. In ICTAI, pages 344-351, 2010.
  12. [Li and Quan, 2010b] Chu Min Li and Zhe Quan. An efficient branch-and-bound algorithm based on maxsat for the maximum clique problem. In AAAI, pages 128-133, 2010.
  13. [Li et al., 2007] Chu Min Li, Felip Manyà, and Jordi Planes. New inference rules for Max-SAT. Journal of Artificial Intelligence Research, 30:321-359, 2007.
  14. [Li et al., 2010a] Chu Min Li, Felip Manyà, Nouredine Ould Mo- hamedou, and Jordi Planes. Resolution-based lower bounds in MaxSAT. Constraints, 15(4):456-484, 2010.
  15. [Li et al., 2010b] Chu Min Li, Felip Manyà, Zhe Quan, and Zhu Zhu. Exact MinSAT solving. In SAT, pages 363-368, 2010.
  16. [Lin et al., 2008] Han Lin, Kaile Su and Chu Min Li. Within- Problem Learning for Efficient Lower Bound Computation in Max-SAT Solving. In AAAI, pages 351-356, 2008.
  17. [Marathe and Ravi, 1996] M. V. Marathe and S. S. Ravi. On ap- proximation algorithms for the minimum satisfiability problem. Information Processing Letters, 58:23-29, 1996.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards