{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T22:49:14Z","timestamp":1742942954049,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031577116"},{"type":"electronic","value":"9783031577123"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-57712-3_8","type":"book-chapter","created":{"date-parts":[[2024,4,18]],"date-time":"2024-04-18T18:02:14Z","timestamp":1713463334000},"page":"113-128","source":"Crossref","is-referenced-by-count":0,"title":["Reduction-Based MAX-3SAT with\u00a0Low Nonlinearity and\u00a0Lattices Under Recombination"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2752-6534","authenticated-orcid":false,"given":"Darrell","family":"Whitley","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7649-5669","authenticated-orcid":false,"given":"Gabriela","family":"Ochoa","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0007-1591-9190","authenticated-orcid":false,"given":"Noah","family":"Floyd","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1259-2990","authenticated-orcid":false,"given":"Francisco","family":"Chicano","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-642-04244-7_13","volume-title":"Principles and Practice of Constraint Programming - CP 2009","author":"C Ans\u00f3tegui","year":"2009","unstructured":"Ans\u00f3tegui, C., Bonet, M.L., Levy, J.: On the structure of industrial SAT instances. In: Gent, I.P. (ed.) Principles and Practice of Constraint Programming - CP 2009. Lecture Notes in Computer Science, vol. 5732, pp. 127\u2013141. Springer, Berlin (2009). https:\/\/doi.org\/10.1007\/978-3-642-04244-7_13"},{"key":"8_CR2","unstructured":"Ans\u00f3tegui, C., Bonet, M.L., Levy, J.: Towards industrial-like random SAT instances. In: IJCAI, vol.\u00a09, pp. 387\u2013392 (2009)"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/978-3-642-14186-7_3","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2010","author":"A Balint","year":"2010","unstructured":"Balint, A., Fr\u00f6hlich, A.: Improving stochastic local search for SAT with a new probability distribution. In: Strichman, O., Szeider, S. (eds.) Theory and Applications of Satisfiability Testing - SAT 2010. Lecture Notes in Computer Science, vol. 6175, pp. 10\u201315. Springer, Berlin (2010). https:\/\/doi.org\/10.1007\/978-3-642-14186-7_3"},{"key":"8_CR4","series-title":"Lecture Notes in Computer Science()","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-030-17462-0_7","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"T Bl\u00e4sius","year":"2019","unstructured":"Bl\u00e4sius, T., Friedrich, T., Sutton, A.M.: On the empirical time complexity of scale-free 3-SAT at the phase transition. In: Vojnar, T., Zhang, L. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science(), vol. 11427, pp. 117\u2013134. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17462-0_7"},{"key":"8_CR5","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1007\/s10878-019-00511-0","volume":"39","author":"E Boros","year":"2020","unstructured":"Boros, E., Crama, Y., Rodriquez-Heck, E.: Compact quadratizations for pseudo-Boolean functions. J. Comb. Optim. 39, 687\u2013707 (2020)","journal-title":"J. Comb. Optim."},{"key":"8_CR6","unstructured":"Boros, E., Gruber, A.: On quadratization of pseudo-Boolean functions (2014). arXiv:1404.6538"},{"issue":"1","key":"8_CR7","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","volume":"123","author":"E Boros","year":"2002","unstructured":"Boros, E., Hammer, P.: Pseudo-Boolean optimization. Discr. Appl. Math. 123(1), 155\u2013225 (2002)","journal-title":"Discr. Appl. Math."},{"issue":"2","key":"8_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1002\/rsa.20057","volume":"27","author":"A Braunstein","year":"2005","unstructured":"Braunstein, A., M\u00e9zard, M., Zecchina, R.: Survey propagation: an algorithm for satisfiability. Random Struct. Algorithms 27(2), 201\u2013226 (2005)","journal-title":"Random Struct. Algorithms"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Chen, W., Whitley, D.: Decomposing SAT instances MAX-kSAT with pseudo backbones. In: European Conference on Evolutionary Computation in Combinatorial Optimization, LNCS, vol. 10197, pp. 75\u201390. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-55453-2_6"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Chen, W., Whitley, D., Tin\u00f3s, R., Chicano, F.: Tunneling between Plateaus: improving on a state-of-the-art MAXSAT solver using partition crossover. In: GECCO Genetic and Evolutionay Computation Conference, pp. 921\u2013928. ACM (2018)","DOI":"10.1145\/3205455.3205482"},{"key":"8_CR11","volume-title":"Introduction to Algorithms","author":"T Cormen","year":"1990","unstructured":"Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms. McGraw Hill, New York (1990)"},{"key":"8_CR12","unstructured":"Dattani, N.: Quadratization in discrete optimization and quantum mechanics (2019). ArXiv:1901.04405"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Dunton, P., Whitley, D.: Reducing the cost of partition crossover on large MAXSAT problems: the PX-preprocessor. In: Genetic and Evolutionary Computation Conference (GECCO-2022), pp. 694\u2013702 (2022)","DOI":"10.1145\/3512290.3528748"},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/11499107_5","volume-title":"Theory and Applications of Satisfiability Testing","author":"N E\u00e9n","year":"2006","unstructured":"E\u00e9n, N., Biere, A.: Effective preprocessing in SAT through variable and clause elimination. In: Bacchus, F., Walsh, T. (eds.) Theory and Applications of Satisfiability Testing. Lecture Notes in Computer Science, vol. 3569, pp. 61\u201375. Springer, Berlin (2006). https:\/\/doi.org\/10.1007\/11499107_5"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1613\/jair.445","volume":"7","author":"J Frank","year":"1997","unstructured":"Frank, J., Cheeseman, P., Stutz, J.: When gravity fails: local search topology. J. Artif. Intell. Res. 7, 249\u2013281 (1997)","journal-title":"J. Artif. Intell. Res."},{"key":"8_CR16","series-title":"Lecture Notes in Computer Science()","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-319-30698-8_11","volume-title":"Evolutionary Computation in Combinatorial Optimization","author":"B Goldman","year":"2016","unstructured":"Goldman, B., Punch, W.: Hyperplane elimination for quickly enumerating local optima. In: Chicano, F., Hu, B., Garcia-Sanchez, P. (eds.) Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science(), vol. 9595, pp. 154\u2013169. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-30698-8_11"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Hains, D., Whitley, D., , Howe, A., Chen, W.: Hyperplane initialized local search for MAXSAT. In: Proceedings of GECCO\u20192009, pp. 805\u2013812 (2013)","DOI":"10.1145\/2463372.2463468"},{"key":"8_CR18","unstructured":"Helsgaun, K.: DIMACS TSP challenge results: current best tours found by LKH (2013). http:\/\/www.akira.ruc.dk\/keld\/research\/LKH\/DIMACS results.html. Accessed 24 Nov 2013"},{"key":"8_CR19","unstructured":"Hoos, H.H.: On the run-time behaviour of stochastic local search algorithms for SAT. In: Proceedings of AAAI, pp. 661\u2013666 (1999)"},{"key":"8_CR20","volume-title":"Stochastic Local Search: Foundations and Applications","author":"H Hoos","year":"2004","unstructured":"Hoos, H., St\u00fctzle, T.: Stochastic Local Search: Foundations and Applications. Morgan Kaufman, Massachusetts (2004)"},{"key":"8_CR21","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780195079517.001.0001","volume-title":"The Origins of Order","author":"S Kauffman","year":"1993","unstructured":"Kauffman, S.: The Origins of Order. Oxford Press, Oxford (1993)"},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"S Kirkpatrick","year":"1994","unstructured":"Kirkpatrick, S., Selman, B.: Critical behavior in the satisfiability of random Boolean expressions. Science 264, 1297\u20131301 (1994)","journal-title":"Science"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Li, C., Manya, F.: MAXSAT, hard and soft constraints. In: Handbook of Satisfiability. IOS Press, Amsterdam (2021)","DOI":"10.3233\/FAIA201007"},{"key":"8_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-540-72788-0_15","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2007","author":"C Lin","year":"2007","unstructured":"Lin, C., Wei, W., Zhang, H.: Combining adaptive noise and look-ahead in local search for SAT. In: Marques-Silva, J., Sakallah, K.A. (eds.) Theory and Applications of Satisfiability Testing - SAT 2007. Lecture Notes in Computer Science, vol. 4501, pp. 121\u2013133. Springer, Berlin (2007). https:\/\/doi.org\/10.1007\/978-3-540-72788-0_15"},{"key":"8_CR25","unstructured":"Selman, B., Levesque, H., Mitchell, D.: A new method for solving hard satisfiability problems. In: AAAI, pp. 44\u2013446 (1992)"},{"key":"8_CR26","doi-asserted-by":"crossref","unstructured":"Selman, B., Kautz, H., Cohen, B.: Local search strategies for satisfiability testing. In: Johnson, D.S., Trick, M.A. (eds.) DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a026. AMS (1996)","DOI":"10.1090\/dimacs\/026\/25"},{"key":"8_CR27","doi-asserted-by":"publisher","unstructured":"Sutton, A.M., Whitley, L.D., Howe, A.E.: A polynomial time computation of the exact correlation structure of k-satisfiability landscapes. In: GECCO 2009, pp. 365\u2013372. ACM (2009). https:\/\/doi.org\/10.1145\/1569901.1569952","DOI":"10.1145\/1569901.1569952"},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"Tin\u00f3s, R., Whitley, D., Chicano, F.: Partition crossover for Pseudo-Boolean optimization. In: Foundations of Genetic Algorithms, (FOGA-15), pp. 137\u2013149 (2015)","DOI":"10.1145\/2725494.2725497"},{"key":"8_CR29","doi-asserted-by":"crossref","unstructured":"Whitley, D., Ochoa, G., Chicano, F.: Partition crossover can linearize local optima lattices of k-bounded Pseudo-Boolean functions. In: Foundations of Genetic Algorithms. ACM (2023)","DOI":"10.1145\/3594805.3607129"}],"container-title":["Lecture Notes in Computer Science","Evolutionary Computation in Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-57712-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,18]],"date-time":"2024-04-18T18:02:24Z","timestamp":1713463344000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-57712-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031577116","9783031577123"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-57712-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]}}}