{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T11:20:29Z","timestamp":1775560829599,"version":"3.50.1"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319232188","type":"print"},{"value":"9783319232195","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23219-5_2","type":"book-chapter","created":{"date-parts":[[2015,8,12]],"date-time":"2015-08-12T10:17:33Z","timestamp":1439374653000},"page":"12-29","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Anytime Hybrid Best-First Search with Tree Decomposition for Weighted CSP"],"prefix":"10.1007","author":[{"given":"David","family":"Allouche","sequence":"first","affiliation":[]},{"given":"Simon","family":"de Givry","sequence":"additional","affiliation":[]},{"given":"George","family":"Katsirelos","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Schiex","sequence":"additional","affiliation":[]},{"given":"Matthias","family":"Zytnicki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,13]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Ans\u00f3tegui, C., Bonet, M.L., Gab\u00e0s, J., Levy, J.: Improving sat-based weighted maxsat solvers. In: Proc. of CP 2012, Qu\u00e9bec City, Canada, pp. 86\u2013101 (2012)","DOI":"10.1007\/978-3-642-33558-7_9"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"van den Berg, J., Shah, R., Huang, A., Goldberg, K.: ANA*: Anytime nonparametric A*. In: Proceedings of Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2011) (2011)","DOI":"10.1609\/aaai.v25i1.7819"},{"key":"2_CR3","unstructured":"Berthold, T.: Primal heuristics for mixed integer programs. Master\u2019s thesis, Technischen Universit\u00e4t Berlin (2006). urn:nbn:de:0297-zib-10293"},{"key":"2_CR4","unstructured":"Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: ECAI, vol. 16, p. 146 (2004)"},{"issue":"7","key":"2_CR5","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1016\/j.artint.2010.02.001","volume":"174","author":"M Cooper","year":"2010","unstructured":"Cooper, M., de Givry, S., Sanchez, M., Schiex, T., Zytnicki, M., Werner, T.: Soft arc consistency revisited. Artificial Intelligence 174(7), 449\u2013478 (2010)","journal-title":"Artificial Intelligence"},{"issue":"2","key":"2_CR6","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.artint.2006.11.003","volume":"171","author":"R Dechter","year":"2007","unstructured":"Dechter, R., Mateescu, R.: And\/or search spaces for graphical models. Artificial Intelligence 171(2), 73\u2013106 (2007)","journal-title":"Artificial Intelligence"},{"key":"2_CR7","unstructured":"de Givry, S., Schiex, T., Verfaillie, G.: Exploiting tree decomposition and soft local consistency in weighted CSP. In: Proc. of the National Conference on Artificial Intelligence, AAAI 2006, pp. 22\u201327 (2006)"},{"key":"2_CR8","unstructured":"Harvey, W.D., Ginsberg, M.L.: Limited discrepency search. In: Proc. of the 14th IJCAI, Montr\u00e9al, Canada (1995)"},{"issue":"1","key":"2_CR9","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0004-3702(02)00400-9","volume":"146","author":"P J\u00e9gou","year":"2003","unstructured":"J\u00e9gou, P., Terrioux, C.: Hybrid backtracking bounded by tree-decomposition of constraint networks. Artif. Intell. 146(1), 43\u201375 (2003)","journal-title":"Artif. Intell."},{"key":"2_CR10","unstructured":"J\u00e9gou, P., Terrioux, C.: Combining restarts, nogoods and decompositions for solving csps. In: Proc. of ECAI 2014, Prague, Czech Republic, pp. 465\u2013470 (2014)"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"J\u00e9gou, P., Terrioux, C.: Tree-decompositions with connected clusters for solving constraint networks. In: Proc. of CP 2014, Lyon, France, pp. 407\u2013423 (2014)","DOI":"10.1007\/978-3-319-10428-7_31"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/978-3-540-85958-1_32","volume-title":"Principles and Practice of Constraint Programming","author":"M Kitching","year":"2008","unstructured":"Kitching, M., Bacchus, F.: Exploiting decomposition in constraint optimization problems. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 478\u2013492. Springer, Heidelberg (2008)"},{"key":"2_CR13","unstructured":"Larrosa, J., de Givry, S., Heras, F., Zytnicki, M.: Existential arc consistency: getting closer to full arc consistency in weighted CSPs. In: Proc. of the 19th IJCAI, pp. 84\u201389, Edinburgh, Scotland (August 2005)"},{"issue":"4","key":"2_CR14","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1287\/opre.14.4.699","volume":"14","author":"E Lawler","year":"1966","unstructured":"Lawler, E., Wood, D.: Branch-and-bound methods: A survey. Operations Research 14(4), 699\u2013719 (1966)","journal-title":"Operations Research"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"1592","DOI":"10.1016\/j.artint.2009.09.002","volume":"173","author":"C Lecoutre","year":"2009","unstructured":"Lecoutre, C., Sa\u00efs, L., Tabary, S., Vidal, V.: Reasoning from last conflict(s) in constraint programming. Artificial Intelligence 173, 1592\u20131614 (2009)","journal-title":"Artificial Intelligence"},{"key":"2_CR16","unstructured":"Likhachev, M., Gordon, G.J., Thrun, S.: ARA*: Anytime A* with provable bounds on sub-optimality. In: Advances in Neural Information Processing Systems, p. None (2003)"},{"issue":"2","key":"2_CR17","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1287\/ijoc.11.2.173","volume":"11","author":"JT Linderoth","year":"1999","unstructured":"Linderoth, J.T., Savelsbergh, M.W.: A computational study of search strategies for mixed integer programming. INFORMS Journal on Computing 11(2), 173\u2013187 (1999)","journal-title":"INFORMS Journal on Computing"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Luby, M., Sinclair, A., Zuckerman, D.: Optimal speedup of las vegas algorithms. In: Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, pp. 128\u2013133. IEEE (1993)","DOI":"10.1109\/ISTCS.1993.253477"},{"key":"2_CR19","unstructured":"Marinescu, R., Dechter, R.: AND\/OR branch-and-bound for graphical models. In: Proc. of IJCAI 2005, Edinburgh, Scotland, UK, pp. 224\u2013229 (2005)"},{"key":"2_CR20","unstructured":"Marinescu, R., Dechter, R.: Best-first AND\/OR search for graphical models. In: Proceedings of the National Conference on Artificial Intelligence, pp. 1171\u20131176. AAAI Press, MIT Press, Menlo Park, Cambridge (1999, 2007)"},{"issue":"3","key":"2_CR21","doi-asserted-by":"crossref","first-page":"211","DOI":"10.3233\/AIC-2012-0531","volume":"25","author":"L Otten","year":"2012","unstructured":"Otten, L., Dechter, R.: Anytime and\/or depth-first search for combinatorial optimization. AI Communications 25(3), 211\u2013227 (2012)","journal-title":"AI Communications"},{"key":"2_CR22","unstructured":"Pearl, J.: Heuristics \u2013 Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishing Comp. (1985)"},{"issue":"3","key":"2_CR23","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0004-3702(70)90007-X","volume":"1","author":"I Pohl","year":"1970","unstructured":"Pohl, I.: Heuristic search viewed as path finding in a graph. Artificial Intelligence 1(3), 193\u2013204 (1970)","journal-title":"Artificial Intelligence"},{"issue":"3","key":"2_CR24","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms 7(3), 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"2_CR25","unstructured":"Sanchez, M., Allouche, D., de Givry, S., Schiex, T.: Russian doll search with tree decomposition. In: IJCAI, pp. 603\u2013608 (2009)"},{"key":"2_CR26","unstructured":"Schulte, C.: Comparing trailing and copying for constraint programming. In: Logic Programming, Las Cruces, New Mexico, USA, pp. 275\u2013289 (1999)"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Stern, R., Kulberis, T., Felner, A., Holte, R.: Using lookaheads with optimal best-first search. In: AAAI (2010)","DOI":"10.1609\/aaai.v24i1.7559"},{"key":"2_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1007\/978-3-540-45193-8_48","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"C Terrioux","year":"2003","unstructured":"Terrioux, C., J\u00e9gou, P.: Bounded backtracking for the valued constraint satisfaction problems. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 709\u2013723. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23219-5_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T23:47:57Z","timestamp":1748562477000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23219-5_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319232188","9783319232195"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23219-5_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"13 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}