{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T09:24:15Z","timestamp":1774257855927,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,8,30]],"date-time":"2018-08-30T00:00:00Z","timestamp":1535587200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci."],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s11704-018-7107-z","type":"journal-article","created":{"date-parts":[[2018,8,30]],"date-time":"2018-08-30T05:11:15Z","timestamp":1535605875000},"page":"86-98","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Empirical investigation of stochastic local search for maximum satisfiability"],"prefix":"10.1007","volume":"13","author":[{"given":"Yi","family":"Chu","sequence":"first","affiliation":[]},{"given":"Chuan","family":"Luo","sequence":"additional","affiliation":[]},{"given":"Shaowei","family":"Cai","sequence":"additional","affiliation":[]},{"given":"Haihang","family":"You","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,30]]},"reference":[{"key":"7107_CR1","first-page":"75","volume-title":"Handbook of Satisfiability","author":"S D Prestwich","year":"2009","unstructured":"Prestwich S D. CNF encodings. Handbook of Satisfiability. 2009, 75\u201397"},{"key":"7107_CR2","first-page":"613","volume":"185","author":"C M Li","year":"2009","unstructured":"Li C M, Many\u00e0 F. MaxSAT, hard and soft constraints. Handbook of Satisfiability, 2009, 185: 613\u2013631","journal-title":"Handbook of Satisfiability"},{"key":"7107_CR3","first-page":"129","volume-title":"Proceedings of Conference of the Canadian Society for Computational Studies of Intelligence","author":"K Smyth","year":"2003","unstructured":"Smyth K, Hoos H H, St\u00fctzle T. Iterated robust tabu search for MAX-SAT. In: Proceedings of Conference of the Canadian Society for Computational Studies of Intelligence. 2003, 129\u2013144"},{"issue":"2\u20133","key":"7107_CR4","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.artint.2006.11.005","volume":"171","author":"Q Yang","year":"2007","unstructured":"Yang Q, Wu K, Jiang Y. Learning action models from plan examples using weighted MAX-SAT. Artificial Intelligence, 2007, 171(2\u20133): 107\u2013143","journal-title":"Artificial Intelligence"},{"issue":"11","key":"7107_CR5","doi-asserted-by":"publisher","first-page":"1804","DOI":"10.1109\/TCAD.2010.2061270","volume":"29","author":"Y Chen","year":"2010","unstructured":"Chen Y, Safarpour S, Marques-Silva J, Veneris A G. Automated design debugging with maximum satisfiability. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29(11): 1804\u20131817","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"7107_CR6","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.cor.2016.08.004","volume":"78","author":"E Demirovic","year":"2017","unstructured":"Demirovic E, Musliu N. MaxSAT-based large neighborhood search for high school timetabling. Computers & Operations Research, 2017, 78: 172\u2013180","journal-title":"Computers & Operations Research"},{"issue":"13","key":"7107_CR7","doi-asserted-by":"publisher","first-page":"134424","DOI":"10.1103\/PhysRevB.94.134424","volume":"94","author":"W Huang","year":"2016","unstructured":"Huang W, Kitchaev D A, Dacek S, Rong Z Q, Urban A, Cao S, Luo C, Ceder G. Finding and proving the exact ground state of a generalized Ising model by convex optimization and MAX-SAT. Physical Review B, 2016, 94(13): 134424","journal-title":"Physical Review B"},{"key":"7107_CR8","first-page":"86","volume-title":"Artifical Intelligence and Statistics","author":"J Berg","year":"2014","unstructured":"Berg J, J\u00e4rvisalo M, Malone B. Learning optimal bounded treewidth bayesian networks via maximum satisfiability. Artifical Intelligence and Statistics. 2014, 86\u201395"},{"key":"7107_CR9","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1613\/jair.2808","volume":"36","author":"H L Chieu","year":"2009","unstructured":"Chieu H L, Lee W S. Relaxed survey propagation for the weighted maximum satisfiability problem. Journal of Artificial Intelligence Research, 2009, 36: 229\u2013266","journal-title":"Journal of Artificial Intelligence Research"},{"key":"7107_CR10","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.artint.2016.11.001","volume":"243","author":"C Luo","year":"2017","unstructured":"Luo C, Cai S, Su K, Huang W. CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability. Artificial Intelligence, 2017, 243: 26\u201344","journal-title":"Artificial Intelligence"},{"key":"7107_CR11","first-page":"2334","volume-title":"Proceedings of IJCAI","author":"H Lin","year":"2007","unstructured":"Lin H, Su K. Exploiting inference rules to compute lower bounds for MAX-SAT solving. In: Proceedings of IJCAI. 2007, 2334\u20132339"},{"key":"7107_CR12","first-page":"351","volume-title":"Proceedings of AAAI","author":"H Lin","year":"2008","unstructured":"Lin H, Su K, Li C M. Within-problem learning for efficient lower bound computation in Max-SAT solving. In: Proceedings of AAAI. 2008, 351\u2013356"},{"key":"7107_CR13","first-page":"467","volume-title":"Exploiting cycle structures in Max-SAT. In: Proceedings of International Conference on Theory and Applications of Satisfiability Testing","author":"C M Li","year":"2009","unstructured":"Li C M, Many\u00e0 F, Mohamedou N O, Planes J, Exploiting cycle structures in Max-SAT. In: Proceedings of International Conference on Theory and Applications of Satisfiability Testing. 2009, 467\u2013480"},{"key":"7107_CR14","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.artint.2013.01.002","volume":"196","author":"C Ans\u00f3tegui","year":"2013","unstructured":"Ans\u00f3tegui C, Bonet M L, Levy J. SAT-based MaxSAT algorithms. Artificial Intelligence, 2013, 196: 77\u2013105","journal-title":"Artificial Intelligence"},{"key":"7107_CR15","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-642-40627-0_12","volume-title":"Proceedings of International Conference on Principles and Practice of Constraint Programming","author":"C Ans\u00f3tegui","year":"2013","unstructured":"Ans\u00f3tegui C, Bonet M L, Gab\u00e0s J, Levy J. Improving WPM2 for (weighted) partial MaxSAT. In: Proceedings of International Conference on Principles and Practice of Constraint Programming. 2013, 117\u2013132"},{"key":"7107_CR16","first-page":"2717","volume-title":"Proceedings of AAAI","author":"N Narodytska","year":"2014","unstructured":"Narodytska N, Bacchus F. Maximum satisfiability using core-guided MaxSAT resolution. In: Proceedings of AAAI. 2014, 2717\u20132723"},{"key":"7107_CR17","volume-title":"Stochastic Local Search: Foundations & Applications","author":"H H Hoos","year":"2004","unstructured":"Hoos H H, St\u00fctzle T. Stochastic Local Search: Foundations & Applications. San Francisoc: Morgan Kaufmann, 2004"},{"key":"7107_CR18","first-page":"2623","volume-title":"Proceedings of AAAI","author":"S Cai","year":"2014","unstructured":"Cai S, Luo C, Thornton J, Su K. Tailoring local search for partial MaxSAT. In: Proceedings of AAAI. 2014, 2623\u20132629"},{"key":"7107_CR19","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1613\/jair.3907","volume":"46","author":"S Cai","year":"2013","unstructured":"Cai S, Su K, Luo C, Sattar A. NuMVC: an efficient local search algorithm for minimum vertex cover. Journal of Artificial Intelligence Research, 2013, 46: 687\u2013716","journal-title":"Journal of Artificial Intelligence Research"},{"key":"7107_CR20","first-page":"747","volume-title":"Proceedings of IJCAI","author":"S Cai","year":"2015","unstructured":"Cai S. Balance between complexity and quality: local search for minimum vertex cover in massive graphs. In: Proceedings of IJCAI. 2015, 747\u2013753"},{"key":"7107_CR21","first-page":"3432","volume-title":"Proceedings of AAAI","author":"Z Zhang","year":"2015","unstructured":"Zhang Z, He H, Luo Z, Qin H, Guo S. An efficient forest-based tabu search algorithm for the split-delivery vehicle routing problem. In: Proceedings of AAAI. 2015, 3432\u20133438"},{"key":"7107_CR22","first-page":"1226","volume-title":"Proceedings of AAAI","author":"S Umetani","year":"2015","unstructured":"Umetani S. Exploiting variable associations to configure efficient local search in large-scale set partitioning problems. In: Proceedings of AAAI. 2015, 1226\u20131232"},{"key":"7107_CR23","first-page":"494","volume-title":"Proceedings of the 30th IEEE\/ACM International Conference on Automated Software Engineering (ASE)","author":"J Lin","year":"2015","unstructured":"Lin J, Luo C, Cai S, Su K, Hao D, Zhang L. TCA: an efficient two-mode meta-heuristic algorithm for combinatorial test generation. In: Proceedings of the 30th IEEE\/ACM International Conference on Automated Software Engineering (ASE). 2015, 494\u2013505"},{"issue":"2","key":"7107_CR24","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s11704-014-3008-y","volume":"8","author":"W Guo","year":"2014","unstructured":"Guo W, Liu G, Chen G, Peng S. A hybrid multi-objective pso algorithm with local search strategy for vlsi partitioning. Frontiers of Computer Science, 2014, 8(2): 203\u2013216","journal-title":"Frontiers of Computer Science"},{"key":"7107_CR25","first-page":"440","volume-title":"Proceedings of AAAI","author":"B Selman","year":"1992","unstructured":"Selman B, Levesque H J, Mitchell D G. A new method for solving hard satisfiability problems. In: Proceedings of AAAI. 1992, 440\u2013446"},{"key":"7107_CR26","first-page":"337","volume-title":"Proceedings of AAAI","author":"B Selman","year":"1994","unstructured":"Selman B, Kautz H A, Cohen B. Noise strategies for improving local search. In: Proceedings of AAAI. 1994, 337\u2013343"},{"key":"7107_CR27","first-page":"20","volume-title":"Proceedings of the 1st International Joint Workshop on Artificial Intelligence and Operations Research","author":"Y Jiang","year":"1995","unstructured":"Jiang Y, Kautz H, Selman B. Solving problems with hard and soft constraints using a stochastic algorithm for MAX-SAT. In: Proceedings of the 1st International Joint Workshop on Artificial Intelligence and Operations Research. 1995, 20"},{"key":"7107_CR28","first-page":"378","volume-title":"Proceedings of IJCAI","author":"B W Wah","year":"1997","unstructured":"Wah B W, Shang Y. Discrete lagrangian-based search for solving MAX-SAT problems. In: Proceedings of IJCAI. 1997, 378\u2013383"},{"issue":"1\/2","key":"7107_CR29","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1023\/A:1006343127545","volume":"24","author":"P Mills","year":"2000","unstructured":"Mills P, Tsang E P K. Guided local search for solving SAT and weighted MAX-SAT problems. Journal of Automated Reasoning, 2000, 24(1\/2): 205\u2013223","journal-title":"Journal of Automated Reasoning"},{"issue":"5","key":"7107_CR30","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1023\/A:1011306011437","volume":"7","author":"M Yagiura","year":"2001","unstructured":"Yagiura M, Ibaraki T. Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT: experimental evaluation. Journal of Heuristics, 2001, 7(5): 423\u2013442","journal-title":"Journal of Heuristics"},{"key":"7107_CR31","first-page":"853","volume-title":"Proceedings of GECCO","author":"K L Sadowski","year":"2013","unstructured":"Sadowski K L, Bosman P A N, Thierens D. On the usefulness of linkage processing for solving MAX-SAT. In: Proceedings of GECCO. 2013, 853\u2013860"},{"key":"7107_CR32","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1145\/2463372.2463468","volume-title":"Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation","author":"D Hains","year":"2013","unstructured":"Hains D, Whitley D, Howe A E, Chen W. Hyperplane initialized local search for MAX-SAT. In: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation. 2013, 805\u2013812"},{"key":"7107_CR33","first-page":"940","volume-title":"Proceedings of AAAI","author":"D Whitley","year":"2013","unstructured":"Whitley D, Howe A E, Hains D. Greedy or not? best improving versus first improving stochastic local search for MAX-SAT. In: Proceedings of AAAI. 2013, 940\u2013946"},{"key":"7107_CR34","first-page":"544","volume-title":"Proceedings of IJCAI","author":"L Kroc","year":"2009","unstructured":"Kroc L, Sabharwal A, Gomes C P, Selman B. Integrating systematic and local search paradigms: a new strategy for MaxSAT. In: Proceedings of IJCAI. 2009, 544\u2013551"},{"key":"7107_CR35","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. Artificial Intelligence, 2013, 204: 75\u201398","journal-title":"Artificial Intelligence"},{"issue":"7","key":"7107_CR36","doi-asserted-by":"publisher","first-page":"1830","DOI":"10.1109\/TC.2014.2346196","volume":"64","author":"C Luo","year":"2015","unstructured":"Luo C, Cai S, Wu W, Jie Z, Su K. CCLS: an efficient local search algorithm for weighted maximum satisfiability. IEEE Transactions on Computers, 2015, 64(7): 1830\u20131843","journal-title":"IEEE Transactions on Computers"},{"key":"7107_CR37","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-319-44953-1_17","volume-title":"Proceedings of International Conference on Principles and Practice of Constraint Programming","author":"J Goffinet","year":"2016","unstructured":"Goffinet J, Ramanujan R. Monte-carlo tree search for the maximum satisfiability problem. In: Proceedings of International Conference on Principles and Practice of Constraint Programming. 2016, 251\u2013267"},{"key":"7107_CR38","volume-title":"MaxSAT solver SC2016","author":"M Wagner","year":"2016","unstructured":"Wagner M. MaxSAT solver SC2016. Max-SAT Evaluation, 2016"},{"key":"7107_CR39","volume-title":"Ramp: a local search solver based on make-positive variables","author":"Y Fan","year":"2016","unstructured":"Fan Y, Ma Z, Su K, Sattar A, Li C. Ramp: a local search solver based on make-positive variables. Max-SAT Evaluation, 2016"},{"key":"7107_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2016.07.006","volume":"240","author":"S Cai","year":"2016","unstructured":"Cai S, Luo C, Lin J, Su K. New local search methods for partial maxsat. Artificial Intelligence, 2016, 240: 1\u201318","journal-title":"Artificial Intelligence"},{"issue":"4","key":"7107_CR41","doi-asserted-by":"crossref","first-page":"139","DOI":"10.3233\/SAT190083","volume":"7","author":"O Roussel","year":"2011","unstructured":"Roussel O. Controlling a solver execution with the runsolver tool. Journal on Satisfiability, Boolean Modeling and Computation, 2011, 7(4): 139\u2013144","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"7107_CR42","first-page":"568","volume-title":"Proceedings of IJCAI","author":"S Cai","year":"2016","unstructured":"Cai S, Lin J. Fast solving maximum weight clique problem in massive graphs. In: Proceedings of IJCAI. 2016, 568\u2013574"},{"key":"7107_CR43","first-page":"805","volume-title":"Proceedings of AAAI","author":"Y Wang","year":"2016","unstructured":"Wang Y, Cai S, Yin M. Two efficient local search algorithms for maximum weight clique problem. In: Proceedings of AAAI. 2016, 805\u2013811"},{"key":"7107_CR44","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1613\/jair.2861","volume":"36","author":"F Hutter","year":"2009","unstructured":"Hutter F, Hoos H H, Leyton-Brown K, St\u00fctzle T. ParamILS: an automatic algorithm configuration framework. Journal of Artificial Intelligence Research, 2009, 36: 267\u2013306","journal-title":"Journal of Artificial Intelligence Research"},{"key":"7107_CR45","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/978-3-642-25566-3_40","volume-title":"Proceedings of Inter national Conference on Learning and Intelligent Optimization","author":"F Hutter","year":"2011","unstructured":"Hutter F, Hoos H H, Leyton-Brown K. Sequential model-based optimization for general algorithm configuration. In: Proceedings of Inter national Conference on Learning and Intelligent Optimization. 2011, 507\u2013523"},{"key":"7107_CR46","first-page":"655","volume-title":"Proceedings of AAAI","author":"H H Hoos","year":"2002","unstructured":"Hoos H H. An adaptive noise mechanism for WalkSAT. In: Proceedings of AAAI. 2002, 655\u2013660"},{"key":"7107_CR47","first-page":"191","volume-title":"Proceedings of AAAI","author":"J Thornton","year":"2004","unstructured":"Thornton J, Pham D N, Bain S, Ferreira Jr V. Additive versus multiplicative clause weighting for SAT. In: Proceedings of AAAI. 2004, 191\u2013196"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11704-018-7107-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-018-7107-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-018-7107-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T21:42:39Z","timestamp":1661895759000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11704-018-7107-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,30]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["7107"],"URL":"https:\/\/doi.org\/10.1007\/s11704-018-7107-z","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,30]]},"assertion":[{"value":"28 March 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}