{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T02:49:39Z","timestamp":1769741379991,"version":"3.49.0"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031377020","type":"print"},{"value":"9783031377037","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T00:00:00Z","timestamp":1689638400000},"content-version":"vor","delay-in-days":198,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Satisfiability Modulo the Theory of Nonlinear Real Arithmetic, SMT(NRA) for short, concerns the satisfiability of <jats:italic>polynomial formulas<\/jats:italic>, which are quantifier-free Boolean combinations of polynomial equations and inequalities with integer coefficients and real variables. In this paper, we propose a local search algorithm for a special subclass of SMT(NRA), where all constraints are strict inequalities. An important fact is that, given a polynomial formula with <jats:italic>n<\/jats:italic> variables, the zero level set of the polynomials in the formula decomposes the <jats:italic>n<\/jats:italic>-dimensional real space into finitely many components (cells) and every polynomial has constant sign in each cell. The key point of our algorithm is a new operation based on real root isolation, called <jats:italic>cell-jump<\/jats:italic>, which updates the current assignment along a given direction such that the assignment can \u2018jump\u2019 from one cell to another. One cell-jump may adjust the values of several variables while traditional local search operations, such as <jats:italic>flip<\/jats:italic> for SAT and <jats:italic>critical move<\/jats:italic> for SMT(LIA), only change that of one variable. We also design a two-level operation selection to balance the success rate and efficiency. Furthermore, our algorithm can be easily generalized to a wider subclass of SMT(NRA) where polynomial equations linear with respect to some variable are allowed. Experiments show the algorithm is competitive with state-of-the-art SMT solvers, and performs particularly well on those formulas with high-degree polynomials.<\/jats:p>","DOI":"10.1007\/978-3-031-37703-7_5","type":"book-chapter","created":{"date-parts":[[2023,7,17]],"date-time":"2023-07-17T17:02:15Z","timestamp":1689613335000},"page":"87-109","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Local Search for\u00a0Solving Satisfiability of\u00a0Polynomial Formulas"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6411-9324","authenticated-orcid":false,"given":"Haokun","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2570-2338","authenticated-orcid":false,"given":"Bican","family":"Xia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5099-0805","authenticated-orcid":false,"given":"Tianqi","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,18]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2020.100633","volume":"119","author":"E \u00c1brah\u00e1m","year":"2021","unstructured":"\u00c1brah\u00e1m, E., Davenport, J.H., England, M., Kremer, G.: Deciding the consistency of non-linear real arithmetic constraints with a conflict driven search using cylindrical algebraic coverings. J. Logical Algebraic Methods Programm. 119, 100633 (2021)","journal-title":"J. Logical Algebraic Methods Programm."},{"key":"5_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-642-31612-8_3","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2012","author":"A Balint","year":"2012","unstructured":"Balint, A., Sch\u00f6ning, U.: Choosing probability distributions for stochastic local search and the role of make versus break. In: Cimatti, A., Sebastiani, R. (eds.) SAT 2012. LNCS, vol. 7317, pp. 16\u201329. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31612-8_3"},{"key":"5_CR3","doi-asserted-by":"publisher","unstructured":"Barbosa, H., et al.: cvc5: a versatile and industrial-strength SMT solver. In: TACAS 2022. LNCS, pp. 415\u2013442. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-99524-9_24","DOI":"10.1007\/978-3-030-99524-9_24"},{"key":"5_CR4","unstructured":"Biere, A.: Splatz, lingeling, plingeling, treengeling, yalsat entering the sat competition 2016. In: Proceedings of SAT Competition, pp. 44\u201345 (2016)"},{"key":"5_CR5","unstructured":"Biere, A., Heule, M., van Maaren, H.: Handbook of Satisfiability, vol. 185. IOS press (2009)"},{"issue":"5","key":"5_CR6","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1006\/jsco.2001.0463","volume":"32","author":"CW Brown","year":"2001","unstructured":"Brown, C.W.: Improved projection for cylindrical algebraic decomposition. J. Symb. Comput. 32(5), 447\u2013465 (2001)","journal-title":"J. Symb. Comput."},{"key":"5_CR7","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.jsc.2014.09.024","volume":"70","author":"CW Brown","year":"2015","unstructured":"Brown, C.W., Ko\u0161ta, M.: Constructing a single cell in cylindrical algebraic decomposition. J. Symb. Comput. 70, 14\u201348 (2015)","journal-title":"J. Symb. Comput."},{"key":"5_CR8","doi-asserted-by":"publisher","unstructured":"Cai, S., Li, B., Zhang, X.: Local search for SMT on linear integer arithmetic. In: International Conference on Computer Aided Verification. pp. 227\u2013248. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-13188-2_12","DOI":"10.1007\/978-3-031-13188-2_12"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.artint.2013.09.001","volume":"204","author":"S Cai","year":"2013","unstructured":"Cai, S., Su, K.: Local search for Boolean satisfiability with configuration checking and subscore. Artif. Intell. 204, 75\u201398 (2013)","journal-title":"Artif. Intell."},{"issue":"3","key":"5_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3230639","volume":"19","author":"A Cimatti","year":"2018","unstructured":"Cimatti, A., Griggio, A., Irfan, A., Roveri, M., Sebastiani, R.: Incremental linearization for satisfiability and verification modulo nonlinear arithmetic and transcendental functions. ACM Trans. Comput. Log. 19(3), 1\u201352 (2018)","journal-title":"ACM Trans. Comput. Log."},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-36742-7_7","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"A Cimatti","year":"2013","unstructured":"Cimatti, A., Griggio, A., Schaafsma, B.J., Sebastiani, R.: The MathSAT5 SMT solver. In: Piterman, N., Smolka, S.A. (eds.) TACAS 2013. LNCS, vol. 7795, pp. 93\u2013107. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36742-7_7"},{"key":"5_CR12","doi-asserted-by":"publisher","unstructured":"Clarke, E.M., Henzinger, T.A., Veith, H., Bloem, R., et al.: Handbook of Model Checking, vol. 10. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-10575-8","DOI":"10.1007\/978-3-319-10575-8"},{"key":"5_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/3-540-07407-4_17","volume-title":"Automata Theory and Formal Languages","author":"GE Collins","year":"1975","unstructured":"Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decompostion. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 134\u2013183. Springer, Heidelberg (1975). https:\/\/doi.org\/10.1007\/3-540-07407-4_17"},{"issue":"3","key":"5_CR14","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0747-7171(08)80152-6","volume":"12","author":"GE Collins","year":"1991","unstructured":"Collins, G.E., Hong, H.: Partial cylindrical algebraic decomposition for quantifier elimination. J. Symb. Comput. 12(3), 299\u2013328 (1991)","journal-title":"J. Symb. Comput."},{"key":"5_CR15","doi-asserted-by":"publisher","unstructured":"De Moura, L., Jovanovi\u0107, D.: A model-constructing satisfiability calculus. In: International Workshop on Verification, Model Checking, and Abstract Interpretation, pp. 1\u201312. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-35873-9_1","DOI":"10.1007\/978-3-642-35873-9_1"},{"key":"5_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1007\/978-3-319-08867-9_49","volume-title":"Computer Aided Verification","author":"B Dutertre","year":"2014","unstructured":"Dutertre, B.: Yices\u00a02.2. In: Biere, A., Bloem, R. (eds.) CAV 2014. LNCS, vol. 8559, pp. 737\u2013744. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-08867-9_49"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Fr\u00f6hlich, A., Biere, A., Wintersteiger, C., Hamadi, Y.: Stochastic local search for satisfiability modulo theories. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 29 (2015)","DOI":"10.1609\/aaai.v29i1.9372"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Glover, F., Laguna, M.: Tabu search. In: Handbook of Combinatorial Optimization, pp. 2093\u20132229. Springer (1998)","DOI":"10.1007\/978-1-4613-0303-9_33"},{"key":"5_CR19","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-642-24364-6_12","volume-title":"Frontiers of Combining Systems","author":"A Griggio","year":"2011","unstructured":"Griggio, A., Phan, Q.-S., Sebastiani, R., Tomasi, S.: Stochastic local search for SMT: combining theory solvers with WalkSAT. In: Tinelli, C., Sofronie-Stokkermans, V. (eds.) FroCoS 2011. LNCS (LNAI), vol. 6989, pp. 163\u2013178. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-24364-6_12"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"Hong, H.: An improvement of the projection operator in cylindrical algebraic decomposition. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, pp. 261\u2013264 (1990)","DOI":"10.1145\/96877.96943"},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-642-31365-3_27","volume-title":"Automated Reasoning","author":"D Jovanovi\u0107","year":"2012","unstructured":"Jovanovi\u0107, D., de Moura, L.: Solving non-linear arithmetic. In: Gramlich, B., Miller, D., Sattler, U. (eds.) IJCAR 2012. LNCS (LNAI), vol. 7364, pp. 339\u2013354. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31365-3_27"},{"key":"5_CR22","doi-asserted-by":"publisher","unstructured":"Lazard, D.: An improved projection for cylindrical algebraic decomposition. In: Algebraic Geometry and its Applications, pp. 467\u2013476. Springer (1994). https:\/\/doi.org\/10.1007\/978-1-4612-2628-4_29","DOI":"10.1007\/978-1-4612-2628-4_29"},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-642-31612-8_43","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2012","author":"CM Li","year":"2012","unstructured":"Li, C.M., Li, Yu.: Satisfying versus falsifying in local search for satisfiability. In: Cimatti, A., Sebastiani, R. (eds.) SAT 2012. LNCS, vol. 7317, pp. 477\u2013478. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31612-8_43"},{"key":"5_CR24","unstructured":"Li, H., Xia, B.: Solving satisfiability of polynomial formulas by sample-cell projection. arXiv preprint arXiv:2003.00409 (2020)"},{"key":"5_CR25","unstructured":"Liu, M., et al.: NRA-LS at the SMT competition 2022. Tool description document, see https:\/\/github.com\/minghao-liu\/NRA-LS (2022)"},{"key":"5_CR26","doi-asserted-by":"publisher","unstructured":"McCallum, S.: An improved projection operation for cylindrical algebraic decomposition. In: Quantifier Elimination and Cylindrical Algebraic Decomposition, pp. 242\u2013268. Springer (1998). https:\/\/doi.org\/10.1007\/978-3-7091-9459-1_12","DOI":"10.1007\/978-3-7091-9459-1_12"},{"key":"5_CR27","unstructured":"Mitchell, D., Selman, B., Leveque, H.: A new method for solving hard satisfiability problems. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp. 440\u2013446 (1992)"},{"key":"5_CR28","doi-asserted-by":"publisher","unstructured":"Moura, L.d., Bj\u00f8rner, N.: Z3: An efficient SMT solver. In: International Conference on Tools and Algorithms for the Construction and Analysis of Systems. pp. 337\u2013340. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-540-78800-3_24","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"Nalbach, J., \u00c1brah\u00e1m, E., Specht, P., Brown, C.W., Davenport, J.H., England, M.: Levelwise construction of a single cylindrical algebraic cell. arXiv preprint arXiv:2212.09309 (2022)","DOI":"10.1016\/j.jsc.2023.02.007"},{"key":"5_CR30","unstructured":"Niemetz, A., Preiner, M.: Ternary propagation-based local search for more bit-precise reasoning. In: 2020 Formal Methods in Computer Aided Design (FMCAD), pp. 214\u2013224. IEEE (2020)"},{"key":"5_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/978-3-319-41528-4_11","volume-title":"Computer Aided Verification","author":"A Niemetz","year":"2016","unstructured":"Niemetz, A., Preiner, M., Biere, A.: Precise and complete propagation based local search for satisfiability modulo theories. In: Chaudhuri, S., Farzan, A. (eds.) CAV 2016. LNCS, vol. 9779, pp. 199\u2013217. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-41528-4_11"},{"key":"5_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-540-27813-9_12","volume-title":"Computer Aided Verification","author":"M Talupur","year":"2004","unstructured":"Talupur, M., Sinha, N., Strichman, O., Pnueli, A.: Range allocation for separation logic. In: Alur, R., Peled, D.A. (eds.) CAV 2004. LNCS, vol. 3114, pp. 148\u2013161. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-27813-9_12"},{"key":"5_CR33","doi-asserted-by":"crossref","unstructured":"Tarski, A.: A decision method for elementary algebra and geometry. University of California Press (1951)","DOI":"10.1525\/9780520348097"},{"issue":"3","key":"5_CR34","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/s10703-017-0284-9","volume":"51","author":"VX Tung","year":"2017","unstructured":"Tung, V.X., Van Khanh, T., Ogawa, M.: raSAT: an SMT solver for polynomial constraints. Formal Methods Syst Design 51(3), 462\u2013499 (2017). https:\/\/doi.org\/10.1007\/s10703-017-0284-9","journal-title":"Formal Methods Syst Design"},{"issue":"2","key":"5_CR35","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s002000050055","volume":"8","author":"V Weispfenning","year":"1997","unstructured":"Weispfenning, V.: Quantifier elimination for real algebra-the quadratic case and beyond. Appl. Algebra Eng. Commun. Comput. 8(2), 85\u2013101 (1997)","journal-title":"Appl. Algebra Eng. Commun. Comput."}],"container-title":["Lecture Notes in Computer Science","Computer Aided Verification"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-37703-7_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T11:03:04Z","timestamp":1693047784000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-37703-7_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031377020","9783031377037"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-37703-7_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"18 July 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CAV","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Computer Aided Verification","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 July 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 July 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"35","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cav2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.i-cav.org\/2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"hotcrp","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"261","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"67","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"11","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}