{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T14:05:54Z","timestamp":1766066754171,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319661575"},{"type":"electronic","value":"9783319661582"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","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":[[2017]]},"DOI":"10.1007\/978-3-319-66158-2_7","type":"book-chapter","created":{"date-parts":[[2017,8,22]],"date-time":"2017-08-22T07:24:38Z","timestamp":1503386678000},"page":"97-113","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Clique Cuts in Weighted Constraint Satisfaction"],"prefix":"10.1007","author":[{"given":"Simon","family":"de Givry","sequence":"first","affiliation":[]},{"given":"George","family":"Katsirelos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,23]]},"reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/978-3-319-23219-5_2","volume-title":"Principles and Practice of Constraint Programming","author":"D Allouche","year":"2015","unstructured":"Allouche, D., de Givry, S., Katsirelos, G., Schiex, T., Zytnicki, M.: Anytime hybrid best-first search with tree decomposition for weighted CSP. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 12\u201329. Springer, Cham (2015). doi: 10.1007\/978-3-319-23219-5_2"},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.artint.2016.06.005","volume":"238","author":"D Allouche","year":"2016","unstructured":"Allouche, D., Bessi\u00e8re, C., Boizumault, P., de Givry, S., Gutierrez, P., Lee, J.H., Leung, K.L., Loudni, S., M\u00e9tivier, J.P., Schiex, T., Wu, Y.: Tractability-preserving transformations of global cost functions. Artif. Intell. 238, 166\u2013189 (2016)","journal-title":"Artif. Intell."},{"key":"7_CR3","unstructured":"Anstegui Gil, C.: Complete SAT solvers for many-valued CNF formulas. Ph.D. thesis, University of Lleida (2004)"},{"issue":"1","key":"7_CR4","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/S0377-2217(99)00015-6","volume":"121","author":"A Atamt\u00fcrk","year":"2000","unstructured":"Atamt\u00fcrk, A., Nemhauser, G.L., Savelsbergh, M.W.: Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. 121(1), 40\u201355 (2000)","journal-title":"Eur. J. Oper. Res."},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-319-09284-3_22","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2014","author":"A Biere","year":"2014","unstructured":"Biere, A., Le Berre, D., Lonca, E., Manthey, N.: Detecting cardinality constraints in CNF. In: Sinz, C., Egly, U. (eds.) SAT 2014. LNCS, vol. 8561, pp. 285\u2013301. Springer, Cham (2014). doi: 10.1007\/978-3-319-09284-3_22"},{"issue":"9","key":"7_CR6","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575\u2013577 (1973)","journal-title":"Commun. ACM"},{"issue":"3","key":"7_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"7_CR8","unstructured":"Cooper, M., de Givry, S., Sanchez, M., Schiex, T., Zytnicki, M.: Virtual arc consistency for weighted CSP. In: Proceedings of AAAI-2008, Chicago, IL (2008)"},{"issue":"7\u20138","key":"7_CR9","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. Artif. Intell. 174(7\u20138), 449\u2013478 (2010)","journal-title":"Artif. Intell."},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-3-642-23786-7_19","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2011","author":"J Davies","year":"2011","unstructured":"Davies, J., Bacchus, F.: Solving MAXSAT by solving a sequence of simpler SAT instances. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 225\u2013239. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-23786-7_19"},{"key":"7_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-642-40627-0_21","volume-title":"Principles and Practice of Constraint Programming","author":"J Davies","year":"2013","unstructured":"Davies, J., Bacchus, F.: Postponing optimization to speed up MAXSAT solving. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 247\u2013262. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40627-0_21"},{"issue":"2","key":"7_CR12","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. Artif. Intell. 171(2), 73\u2013106 (2007)","journal-title":"Artif. Intell."},{"key":"7_CR13","unstructured":"Dixon, H.E.: Automating psuedo-Boolean inference within a DPLL framework. Ph.D. thesis, University of Oregon (2004)"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/978-3-642-40627-0_22","volume-title":"Principles and Practice of Constraint Programming","author":"S Givry de","year":"2013","unstructured":"de Givry, S., Prestwich, S.D., O\u2019Sullivan, B.: Dead-end elimination for weighted CSP. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 263\u2013272. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40627-0_22"},{"key":"7_CR15","unstructured":"de Givry, S., Schiex, T., Verfaillie, G.: Exploiting tree decomposition and soft local consistency in weighted CSP. In: Proceedings of AAAI-2006, Boston, MA (2006)"},{"key":"7_CR16","unstructured":"de Givry, S., Zytnicki, M., Heras, F., Larrosa, J.: Existential arc consistency: getting closer to full arc consistency in weighted CSPs. In: Proceedings of IJCAI-2005, Edinburgh, Scotland, pp. 84\u201389 (2005)"},{"key":"7_CR17","unstructured":"Globerson, A., Jaakkola, T.: Fixing max-product: convergent message passing algorithms for MAP LP-relaxations. In: Proceedings of NIPS, Vancouver, Canada (2007)"},{"issue":"4\u20135","key":"7_CR18","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s10732-006-6550-4","volume":"12","author":"WJ Hoeve van","year":"2006","unstructured":"van Hoeve, W.J., Pesant, G., Rousseau, L.: On global warming: flow-based soft global constraints. J. Heuristics 12(4\u20135), 347\u2013373 (2006)","journal-title":"J. Heuristics"},{"issue":"3","key":"7_CR19","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/s10601-016-9245-y","volume":"21","author":"B Hurley","year":"2016","unstructured":"Hurley, B., O\u2019Sullivan, B., Allouche, D., Katsirelos, G., Schiex, T., Zytnicki, M., de Givry, S.: Multi-language evaluation of exact solvers in graphical model discrete optimization. Constraints 21(3), 413\u2013434 (2016)","journal-title":"Constraints"},{"issue":"1","key":"7_CR20","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":"7_CR21","unstructured":"Kask, K., Dechter, R.: Branch and bound with mini-bucket heuristics. In: Proceedings of IJCAI-1999. vol. 99, pp. 426\u2013433 (1999)"},{"issue":"3","key":"7_CR22","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1016\/j.ejor.2007.06.069","volume":"199","author":"MOI Khemmoudj","year":"2009","unstructured":"Khemmoudj, M.O.I., Bennaceur, H.: Clique inference process for solving Max-CSP. Eur. J. Oper. Res. 199(3), 665\u2013673 (2009)","journal-title":"Eur. J. Oper. Res."},{"issue":"10","key":"7_CR23","doi-asserted-by":"publisher","first-page":"1568","DOI":"10.1109\/TPAMI.2006.200","volume":"28","author":"V Kolmogorov","year":"2006","unstructured":"Kolmogorov, V.: Convergent tree-reweighted message passing for energy minimization. IEEE Pattern Anal. Mach. Intell. 28(10), 1568\u20131583 (2006)","journal-title":"IEEE Pattern Anal. Mach. Intell."},{"key":"7_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/3-540-45349-0_22","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2000","author":"J Larrosa","year":"2000","unstructured":"Larrosa, J.: Boosting search with variable elimination. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 291\u2013305. Springer, Heidelberg (2000). doi: 10.1007\/3-540-45349-0_22"},{"key":"7_CR25","unstructured":"Larrosa, J., Schiex, T.: In the quest of the best form of local consistency for weighted CSP. In: Proceedings of 18th IJCAI, Acapulco, Mexico, pp. 239\u2013244 (2003)"},{"key":"7_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-642-33558-7_31","volume-title":"Principles and Practice of Constraint Programming","author":"C Lecoutre","year":"2012","unstructured":"Lecoutre, C., Roussel, O., Dehani, D.E.: WCSP integration of soft neighborhood substitutability. In: Milano, M. (ed.) CP 2012. LNCS, pp. 406\u2013421. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-33558-7_31"},{"key":"7_CR27","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1613\/jair.3476","volume":"43","author":"JHM Lee","year":"2012","unstructured":"Lee, J.H.M., Leung, K.L.: Consistency techniques for global cost functions in weighted constraint satisfaction. J. Artif. Intell. R. 43, 257\u2013292 (2012)","journal-title":"J. Artif. Intell. R."},{"key":"7_CR28","doi-asserted-by":"crossref","unstructured":"Lee, J.H., Leung, K.L.: A stronger consistency for soft global constraints in weighted constraint satisfaction. In: Proceedings of AAAI-2010, Atlanta, USA (2010)","DOI":"10.1609\/aaai.v24i1.7550"},{"key":"7_CR29","unstructured":"Marinescu, R., Dechter, R.: AND\/OR branch-and-bound for graphical models. In: Proceedings of IJCAI-2005, Edinburgh, Scotland, UK, pp. 224\u2013229 (2005)"},{"key":"7_CR30","doi-asserted-by":"crossref","unstructured":"Narodytska, N., Bacchus, F.: Maximum satisfiability using core-guided MAXSAT resolution. In: Proceedings of AAAI-2014, Quebec City, Canada, pp. 2717\u20132723 (2014)","DOI":"10.1609\/aaai.v28i1.9124"},{"issue":"2","key":"7_CR31","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/s10601-016-9250-1","volume":"22","author":"H Nguyen","year":"2016","unstructured":"Nguyen, H., Bessiere, C., de Givry, S., Schiex, T.: Triangle-based consistencies for cost function networks. Constraints 22(2), 230\u2013264 (2016)","journal-title":"Constraints"},{"key":"7_CR32","doi-asserted-by":"crossref","unstructured":"Prusa, D., Werner, T.: Universality of the local marginal polytope. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 1738\u20131743 (2013)","DOI":"10.1109\/CVPR.2013.227"},{"key":"7_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1007\/11889205_64","volume-title":"Principles and Practice of Constraint Programming - CP 2006","author":"C-G Quimper","year":"2006","unstructured":"Quimper, C.-G., Walsh, T.: Global grammar constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 751\u2013755. Springer, Heidelberg (2006). doi: 10.1007\/11889205_64"},{"key":"7_CR34","unstructured":"Quimper, C., Walsh, T.: Decompositions of grammar constraints. CoRR abs\/0903.0470 (2009)"},{"issue":"1","key":"7_CR35","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/s10601-007-9029-5","volume":"13","author":"M S\u00e1nchez","year":"2008","unstructured":"S\u00e1nchez, M., de Givry, S., Schiex, T.: Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques. Constraints 13(1), 130\u2013154 (2008)","journal-title":"Constraints"},{"key":"7_CR36","first-page":"113","volume":"4","author":"MI Schlesinger","year":"1976","unstructured":"Schlesinger, M.I.: Syntactic analysis of two-dimensional visual signals in noisy conditions. Kibernetika 4, 113\u2013130 (1976). (in Russian)","journal-title":"Kibernetika"},{"key":"7_CR37","unstructured":"Sontag, D., Choe, D., Li, Y.: Efficiently searching for frustrated cycles in MAP inference. In: Proceedings of UAI, pp. 795\u2013804 (2012)"},{"key":"7_CR38","unstructured":"Sontag, D., Meltzer, T., Globerson, A., Weiss, Y., Jaakkola, T.: Tightening LP relaxations for MAP using message-passing. In: Proceedings of UAI, pp. 503\u2013510 (2008)"},{"issue":"7","key":"7_CR39","doi-asserted-by":"publisher","first-page":"1165","DOI":"10.1109\/TPAMI.2007.1036","volume":"29","author":"T Werner","year":"2007","unstructured":"Werner, T.: A linear programming approach to max-sum problem: a review. IEEE Trans. Pattern Anal. Mach. Intell. 29(7), 1165\u20131179 (2007). https:\/\/doi.org\/10.1109\/TPAMI.2007.1036","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-66158-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T05:24:31Z","timestamp":1692941071000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-66158-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319661575","9783319661582"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-66158-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"23 August 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Principles and Practice of Constraint Programming","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Melbourne","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Australia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 August 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 September 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cp2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cp2017.a4cp.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}