[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Inference in MaxSAT and MinSAT

  • Chapter
  • First Online:
The Logic of Software. A Tasting Menu of Formal Methods

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13360))

Abstract

Logical calculi applied to solve SAT are unsound for MaxSAT and MinSAT because they preserve satisfiability but not the minimum and the maximum number of unsatisfied clauses, respectively. This paper overviews the complete resolution and tableau-style calculi that have been defined to solve MaxSAT and MinSAT, as well as their variants with hard and weighted soft clauses. These calculi provide an exact approach to solving MaxSAT and MinSAT problems.

This work has been supported by the French Agence Nationale de la Recherche, reference ANR-19-CHIA-0013-01, and Grant PID2019-111544GB-C21 funded by MCIN/AEI/10.13039/501100011033. The last author was supported by mobility grant PRX21/00488 of the Spanish Ministerio de Universidades.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 71.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Abramé, A., Habet, D.: Ahmaxsat: description and evaluation of a branch and bound Max-SAT solver. J. Satisfiability Boolean Modeling Comput. 9, 89–128 (2014)

    Article  MathSciNet  Google Scholar 

  2. Abramé, A., Habet, D.: Local search algorithm for the partial minimum satisfiability problem. In: Proceedings of the 27th IEEE International Conference on Tools with Artificial Intelligence, ICTAI, Vietri sul Mare, Italy, pp. 821–827 (2015)

    Google Scholar 

  3. Ansótegui, C., Bonet, M.L., Levy, J., Manyà, F.: Inference rules for high-order consistency in weighted CSP. In: Proceedings of the 22nd AAAI Conference on Artificial Intelligence, Vancouver, Canada, pp. 167–172 (2007)

    Google Scholar 

  4. Ansótegui, C., Bonet, M.L., Levy, J., Manyà, F.: The logic behind weighted CSP. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAI-2007, Hyderabad, India, pp. 32–37 (2007)

    Google Scholar 

  5. Ansótegui, C., Bonet, M.L., Levy, J., Manyà, F.: Resolution procedures for multiple-valued optimization. Inf. Sci. 227, 43–59 (2013)

    Article  MathSciNet  Google Scholar 

  6. Ansótegui, C., Izquierdo, I., Manyà, F., Jiménez, J.T.: A Max-SAT-based approach to constructing optimal covering arrays. In: Proceedings of the 16th International Conference of the Catalan Association for Artificial Intelligence, CCIA 2013, Vic, Spain. Frontiers in Artificial Intelligence and Applications, vol. 256, pp. 51–59. IOS Press (2013)

    Google Scholar 

  7. Ansótegui, C., Levy, J.: Reducing SAT to Max2SAT. In: Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI-2021, Montreal, Canada, pp. 193–198 (2021)

    Google Scholar 

  8. Ansótegui, C., Li, C.M., Manyà, F., Zhu, Z.: A SAT-based approach to MinSAT. In: Proceedings of the 15th International Conference of the Catalan Association for Artificial Intelligence, CCIA-2012, Alacant, Spain, pp. 185–189. IOS Press (2012)

    Google Scholar 

  9. Ansótegui, C., Manyà, F., Ojeda, J., Salvia, J.M., Torres, E.: Incomplete MaxSAT approaches for combinatorial testing. J. Heuristics (2022, in press)

    Google Scholar 

  10. Argelich, J., Li, C.M., Manyà, F., Planes, J.: The first and second Max-SAT evaluations. J. Satisfiability Boolean Modeling Comput. 4(2–4), 251–278 (2008)

    Article  Google Scholar 

  11. Argelich, J., Li, C.M., Manyà, F., Soler, J.R.: Clause tableaux for maximum and minimum satisfiability. Logic J. IGPL 29(1), 7–27 (2021)

    Article  MathSciNet  Google Scholar 

  12. Bacchus, F., Berg, J., Järvisalo, M., Martins, R.: MaxSAT Evaluation 2020: Solver and Benchmark Descriptions. University of Helsinki, Department of Computer Science (2020)

    Google Scholar 

  13. Bacchus, F., Järvisalo, M., Ruben, M.: Maximum satisfiability. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability, pp. 929–991. IOS Press, Amsterdam (2021)

    Google Scholar 

  14. Beckert, B., Hähnle, R., Manyà, F.: The SAT problem of signed CNF formulas. In: Basin, D., D’Agostino, M., Gabbay, D., Matthews, S., Viganò, L. (eds.) Labelled Deduction. Applied Logic Series, vol. 17, pp. 61–82. Kluwer, Dordrecht (2000)

    Chapter  Google Scholar 

  15. Bofill, M., Garcia, M., Suy, J., Villaret, M.: MaxSAT-based scheduling of B2B meetings. In: Proceedings of the12th International Conference on Integration of AI and OR Techniques in Constraint Programming, CPAIOR, Barcelona, Spain, pp. 65–73 (2015)

    Google Scholar 

  16. Bonet, M.L., Buss, S., Ignatiev, A., Marques-Silva, J., Morgado, A.: MaxSAT resolution with the dual rail encoding. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence, AAAI, New Orleans, Louisiana, USA, pp. 6565–6572 (2018)

    Google Scholar 

  17. Bonet, M.L., Levy, J.: Equivalence between systems stronger than resolution. In: Pulina, L., Seidl, M. (eds.) SAT 2020. LNCS, vol. 12178, pp. 166–181. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51825-7_13

    Chapter  Google Scholar 

  18. Bonet, M.L., Levy, J., Manyà, F.: A complete calculus for Max-SAT. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 240–251. Springer, Heidelberg (2006). https://doi.org/10.1007/11814948_24

    Chapter  MATH  Google Scholar 

  19. Bonet, M.L., Levy, J., Manyà, F.: Resolution for Max-SAT. Artif. Intell. 171(8–9), 240–251 (2007)

    MathSciNet  MATH  Google Scholar 

  20. Cai, S., Lei, Z.: Old techniques in new ways: clause weighting, unit propagation and hybridization for maximum satisfiability. Artif. Intell. 287, 103354 (2020)

    Article  MathSciNet  Google Scholar 

  21. Casas-Roma, J., Huertas, A., Manyà, F.: Solving MaxSAT with natural deduction. In: Proceedings of the 20th International Conference of the Catalan Association for Artificial Intelligence, Deltebre, Spain. Frontiers in Artificial Intelligence and Applications, vol. 300, pp. 186–195. IOS Press (2017)

    Google Scholar 

  22. D’Agostino, M.: Tableaux methods for classical propositional logic. In: D’Agostino, M., Gabbay, D., Hähnle, R., Posegga, J. (eds.) Handbook of Tableau Methods, pp. 45–123. Kluwer (1999)

    Google Scholar 

  23. D’Almeida, D., Grégoire, É.: Model-based diagnosis with default information implemented through MAX-SAT technology. In: Proceedings of the IEEE 13th International Conference on Information Reuse & Integration, IRI, Las Vegas, NV, USA, pp. 33–36 (2012)

    Google Scholar 

  24. Fiorino, G.: New tableau characterizations for non-clausal MaxSAT problem. Logic J. IGPL (2021). https://doi.org/10.1093/jigpal/jzab012

    Article  Google Scholar 

  25. Fiorino, G.: A non-clausal tableau calculus for MinSAT. Inf. Process. Lett. 173, 106167 (2022)

    Article  MathSciNet  Google Scholar 

  26. Guerra, J., Lynce, I.: Reasoning over biological networks using maximum satisfiability. In: Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming, CP, Québec City, QC, Canada, pp. 941–956 (2012)

    Google Scholar 

  27. Hähnle, R.: Tableaux and related methods. In: Robinson, J.A., Voronkov, A. (eds.) Handbook of Automated Reasoning, pp. 100–178. Elsevier and MIT Press (2001)

    Google Scholar 

  28. Haken, A.: The intractability of resolution. Theoret. Comput. Sci. 39, 297–308 (1985)

    Article  MathSciNet  Google Scholar 

  29. Heras, F., Larrosa, J.: New inference rules for efficient Max-SAT solving. In: Proceedings of the National Conference on Artificial Intelligence, AAAI-2006, Boston/MA, USA, pp. 68–73 (2006)

    Google Scholar 

  30. Heras, F., Larrosa, J., Oliveras, A.: MiniMaxSAT: an efficient weighted Max-SAT solver. J. Artif. Intell. Res. 31, 1–32 (2008)

    Article  MathSciNet  Google Scholar 

  31. Ignatiev, A., Morgado, A., Marques-Silva, J.: On tackling the limits of resolution in SAT solving. In: Gaspers, S., Walsh, T. (eds.) SAT 2017. LNCS, vol. 10491, pp. 164–183. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66263-3_11

    Chapter  MATH  Google Scholar 

  32. Jabbour, S., Mhadhbi, N., Raddaoui, B., Sais, L.: A SAT-based framework for overlapping community detection in networks. In: Proceedings of the 21st Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, Part II, PAKDD, Jeju, South Korea, pp. 786–798 (2017)

    Google Scholar 

  33. Kuegel, A.: Improved exact solver for the weighted MAX-SAT problem. In: Proceedings of Workshop Pragmatics of SAT, POS-10, Edinburgh, UK, pp. 15–27 (2010)

    Google Scholar 

  34. Larrosa, J., Heras, F.: Resolution in Max-SAT and its relation to local consistency in weighted CSPs. In: Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI-2005, Edinburgh, Scotland, pp. 193–198. Morgan Kaufmann (2005)

    Google Scholar 

  35. Larrosa, J., Rollon, E.: Towards a better understanding of (partial weighted) MaxSAT proof systems. In: Pulina, L., Seidl, M. (eds.) SAT 2020. LNCS, vol. 12178, pp. 218–232. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51825-7_16

    Chapter  MATH  Google Scholar 

  36. Li, C.M., Manyà, F.: MaxSAT, hard and soft constraints. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability, pp. 903–927. IOS Press (2021)

    Google Scholar 

  37. Li, C.M., Manyà, F.: An exact inference scheme for MinSAT. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence, IJCAI-2015, Buenos Aires, Argentina, pp. 1959–1965 (2015)

    Google Scholar 

  38. 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). https://doi.org/10.1007/11564751_31

    Chapter  MATH  Google Scholar 

  39. Li, C.M., Manyà, F., Planes, J.: Detecting disjoint inconsistent subformulas for computing lower bounds for Max-SAT. In: Proceedings of the 21st National Conference on Artificial Intelligence, AAAI-2006, Boston/MA, USA, pp. 86–91 (2006)

    Google Scholar 

  40. Li, C.M., Manyà, F., Planes, J.: New inference rules for Max-SAT. J. Artif. Intell. Res. 30, 321–359 (2007)

    Article  MathSciNet  Google Scholar 

  41. Li, C.M., Manyà, F., Soler, J.R.: A clause tableaux calculus for MaxSAT. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence, IJCAI-2016, New York, USA, pp. 766–772 (2016)

    Google Scholar 

  42. Li, C.M., Manyà, F., Soler, J.R.: Clausal form transformation in MaxSAT. In: Proceedings of the 49th IEEE International Symposium on Multiple-Valued Logic, ISMVL, Fredericton, Canada, pp. 132–137 (2019)

    Google Scholar 

  43. Li, C.M., Manyà, F., Soler, J.R.: A tableau calculus for non-clausal maximum satisfiability. In: Cerrito, S., Popescu, A. (eds.) TABLEAUX 2019. LNCS (LNAI), vol. 11714, pp. 58–73. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-29026-9_4

    Chapter  Google Scholar 

  44. Li, C.M., Manyà, F., Soler, J.R., Vidal, A.: From non-clausal to clausal MinSAT. In: Proceedings of the 23rd International Conference of the Catalan Association for Artificial Intelligence, CCIA, Lleida, Spain, pp. 27–36. IOS Press (2021)

    Google Scholar 

  45. Li, C.M., Xiao, F., Manyà, F.: A resolution calculus for MinSAT. Logic J. IGPL 29(1), 28–44 (2021)

    Article  MathSciNet  Google Scholar 

  46. Li, C.-M., Zhenxing, X., Coll, J., Manyà, F., Habet, D., He, K.: Boosting branch-and-bound MaxSAT solvers with clause learning. AI Commun. (2021). https://doi.org/10.3233/AIC-210178

    Article  Google Scholar 

  47. Li, C.-M., Xu, Z., Coll, J., Manyà, F., Habet, D., He, K.: Combining clause learning and branch and bound for MaxSAT. In: Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming, CP, Montpellier, France. LIPIcs, vol. 210, pp. 38:1–38:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

    Google Scholar 

  48. Li, C.M., Zhu, Z., Manyà, F., Simon, L.: Minimum satisfiability and its applications. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI-2011, Barcelona, Spain, pp. 605–610 (2011)

    Google Scholar 

  49. Li, C.M., Zhu, Z., Manyà, F., Simon, L.: Optimizing with minimum satisfiability. Artif. Intell. 190, 32–44 (2012)

    Article  MathSciNet  Google Scholar 

  50. Manyà, F., Negrete, S., Roig, C., Soler, J.R.: A MaxSAT-based approach to the team composition problem in a classroom. In: Sukthankar, G., Rodriguez-Aguilar, J.A. (eds.) AAMAS 2017. LNCS (LNAI), vol. 10643, pp. 164–173. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71679-4_11

    Chapter  Google Scholar 

  51. Manyà, F., Negrete, S., Roig, C., Soler, J.R.: Solving the team composition problem in a classroom. Fundamamenta Informaticae 174(1), 83–101 (2020)

    Article  MathSciNet  Google Scholar 

  52. Marques-Silva, J., Argelich, J., Graça, A., Lynce, I.: Boolean lexicographic optimization: algorithms & applications. Ann. Math. Artif. Intell. 62(3–4), 317–343 (2011)

    Article  MathSciNet  Google Scholar 

  53. Mundici, D.: Ulam game, the logic of MaxSAT, and many-valued partitions. In: Prade, H., Dubois, D., Klement, E.P. (eds.) Logics and Reasoning about Knowledge, pp. 121–137. Kluwer (1999)

    Google Scholar 

  54. Mundici, D., Olivetti, N.: Resolution and model building in the infinitely-valued calculus of Łukasiewicz. Theoret. Comput. Sci. 200(1–2), 335–366 (1998)

    Article  MathSciNet  Google Scholar 

  55. Narodytska, N., Bacchus, F.: Maximum satisfiability using core-guided MaxSAT resolution. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence, Québec City, Canada, pp. 2717–2723 (2014)

    Google Scholar 

  56. Olivetti, N.: Tableaux for Łukasiewicz infinite-valued logic. Stud. Logica. 73(1), 81–111 (2003)

    Article  Google Scholar 

  57. Py, M., Cherif, M.S., Habet, D.: A proof builder for max-SAT. In: Li, C.-M., Manyà, F. (eds.) SAT 2021. LNCS, vol. 12831, pp. 488–498. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-80223-3_33

    Chapter  MATH  Google Scholar 

  58. Robinson, J.A.: A machine oriented logic based on the resolution principle. J. ACM 12(1), 23–41 (1965)

    Article  MathSciNet  Google Scholar 

  59. Safarpour, S., Mangassarian, H., Veneris, A.G., Liffiton, M.H., Sakallah, K.A.: Improved design debugging using maximum satisfiability. In: Proceedings of 7th International Conference on Formal Methods in Computer-Aided Design, FMCAD, Austin, Texas, USA, pp. 13–19 (2007)

    Google Scholar 

  60. Smullyan, R.: First-Order Logic. Dover Publications, New York, second corrected edition (1995). First published 1968 by Springer-Verlag

    Google Scholar 

  61. Warner, H.: A new resolution calculus for the infinite-valued propositional logic of Łukasiewicz. In: Proceedings of the International Workshop on First order Theorem Proving, pp. 234–243 (1998)

    Google Scholar 

  62. Xu, H., Rutenbar, R.A., Sakallah, K.A.: sub-SAT: a formulation for relaxed boolean satisfiability with applications in routing. IEEE Trans. CAD Integr. Circuits Syst. 22(6), 814–820 (2003)

    Article  Google Scholar 

  63. Zhang, L., Bacchus, F.: MAXSAT heuristics for cost optimal planning. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence, Toronto, Ontario, Canada, pp. 1846–1852 (2012)

    Google Scholar 

Download references

Acknowledgments

We thank the reviewers for their valuable comments and suggestions, which greatly improved this manuscript. We also want to congratulate Reiner Hähnle on his 60th birthday, as well as thank Bernhard Beckert, Einar Broch Johnsen, Richard Bubel, and Wolfgang Ahrendt for organizing a symposium and Festschrift in honor of Reiner Hähnle.

Author information

Authors and Affiliations

  1. MIS, Université de Picardie Jules Verne, Amiens, France

    Chu Min Li

  2. Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France

    Chu Min Li

  3. Artificial Intelligence Research Institute (IIIA, CSIC), Bellaterra, Spain

    Felip Manyà

Authors
  1. Chu Min Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Felip Manyà
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Felip Manyà .

Editor information

Editors and Affiliations

  1. Chalmers University of Technology, Gothenburg, Sweden

    Wolfgang Ahrendt

  2. Karlsruhe Institute of Technology, Karlsruhe, Germany

    Bernhard Beckert

  3. TU Darmstadt, Darmstadt, Germany

    Richard Bubel

  4. University of Oslo, Oslo, Norway

    Einar Broch Johnsen

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Li, C.M., Manyà, F. (2022). Inference in MaxSAT and MinSAT. In: Ahrendt, W., Beckert, B., Bubel, R., Johnsen, E.B. (eds) The Logic of Software. A Tasting Menu of Formal Methods. Lecture Notes in Computer Science, vol 13360. Springer, Cham. https://doi.org/10.1007/978-3-031-08166-8_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-08166-8_16

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-08165-1

  • Online ISBN: 978-3-031-08166-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation