{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:18:25Z","timestamp":1780633105188,"version":"3.54.1"},"publisher-location":"Cham","reference-count":99,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030061661","type":"print"},{"value":"9783030061678","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"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":[[2020]]},"DOI":"10.1007\/978-3-030-06167-8_7","type":"book-chapter","created":{"date-parts":[[2020,5,8]],"date-time":"2020-05-08T00:02:20Z","timestamp":1588896140000},"page":"185-207","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Valued Constraint Satisfaction Problems"],"prefix":"10.1007","author":[{"given":"Martin C.","family":"Cooper","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simon","family":"de Givry","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schiex","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,5,8]]},"reference":[{"key":"7_CR1","volume-title":"Local search in combinatorial optimization","author":"E Aarts","year":"1997","unstructured":"Aarts E, Lenstra J (1997) Local search in combinatorial optimization. Interscience series in discrete mathematics and optimization, Wiley, New York"},{"issue":"2","key":"7_CR2","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1109\/18.825794","volume":"46","author":"S Aji","year":"2000","unstructured":"Aji S, McEliece R (2000) The generalized distributive law. IEEE Trans Inf Theory 46(2):325\u2013343","journal-title":"IEEE Trans Inf Theory"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1051\/ro\/2013032","volume":"47","author":"M Akplogan","year":"2013","unstructured":"Akplogan M, de Givry S, M\u00e9tivier JP, Quesnel G, Joannon A, Garcia F (2013) Solving the crop allocation problem using hard and soft constraints. RAIRO - Oper Res 47:151\u2013172","journal-title":"RAIRO - Oper Res"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Allouche D, de\u00a0Givry S, Schiex T (2010) Towards parallel non serial dynamic programming for solving hard weighted CSP. In: Proceedings of CP-10, St Andrews, Scotland, pp 53\u201360","DOI":"10.1007\/978-3-642-15396-9_7"},{"key":"7_CR5","unstructured":"Allouche D, Bessiere C, Boizumault P, de\u00a0Givry S, M\u00e9tivier J, Gutierrez P, Loudni S, Schiex T (2012) Filtering decomposable global cost functions. In: Proceedings of AAAI-12, Toronto, Canada, pp 407\u2013413"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.artint.2014.03.005","volume":"212","author":"D Allouche","year":"2014","unstructured":"Allouche D, Andr\u00e9 I, Barbe S, Davies J, de Givry S, Katsirelos G, O\u2019Sullivan B, Prestwich S, Schiex T, Traor\u00e9 S (2014) Computational protein design as an optimization problem. Artif Intell 212:59\u201379","journal-title":"Artif Intell"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Allouche D, de\u00a0Givry S, Katsirelos G, Schiex T, Zytnicki M (2015) Anytime hybrid best-first search with tree decomposition for weighted CSP. In: Proceedings of CP-15, Cork, Ireland, pp 12\u201328","DOI":"10.1007\/978-3-319-23219-5_2"},{"key":"7_CR8","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, Bessiere C, Boizumault P, de Givry S, Gutierrez P, Lee J, Leung K, Loudni S, M\u00e9tivier J, Schiex T, Wu Y (2016) Tractability-preserving transformations of global cost functions. Artif Intell J 238:166\u2013189","journal-title":"Artif Intell J"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Alphonse E, Rouveirol C (2007) Extension of the top-down data-driven strategy to ILP. In: Inductive Logic Programming. Springer, pp 49\u201363","DOI":"10.1007\/978-3-540-73847-3_13"},{"key":"7_CR10","unstructured":"Bacchus F, Grove A (1995) Graphical models for preference and utility. In: Proceedings of UAI-95, Montreal, Quebec, Canada, pp 3\u201310"},{"key":"7_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42849-9","volume-title":"Decision diagrams for optimization","author":"D Bergman","year":"2016","unstructured":"Bergman D, Cire AA, van Hoeve WJ, Hooker J (2016) Decision diagrams for optimization. Springer, Berlin"},{"key":"7_CR12","unstructured":"Bertel\u00e9 U, Brioshi F (1972) Nonserial Dynamic Programming. Academic Press, London"},{"key":"7_CR13","unstructured":"Bistarelli S, Montanari U, Rossi F (1995) Constraint solving over semirings. In: Proceedings of IJCAI-95, Montr\u00e9al, Canada"},{"issue":"2","key":"7_CR14","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/256303.256306","volume":"44","author":"S Bistarelli","year":"1997","unstructured":"Bistarelli S, Montanari U, Rossi F (1997) Semiring-based constraint satisfaction and optimization. J ACM 44(2):201\u2013236","journal-title":"J ACM"},{"key":"7_CR15","unstructured":"Bodlaender H, Koster A (2008) Treewidth Computations I. Upper Bounds. Technical Report UU-CS-2008-032, Utrecht University, Department of Information and Computing Sciences, Utrecht, The Netherlands"},{"key":"7_CR16","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 (2002) Pseudo-boolean optimization. Discret Appl Math 123:155\u2013225","journal-title":"Discret Appl Math"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Bresler M, Prusa D, Hlav\u00e1c V (2013) Modeling flowchart structure recognition as a max-sum problem. 12th International Conference on Document Analysis and Recognition. USA, Washington, DC, pp 1215\u20131219","DOI":"10.1109\/ICDAR.2013.246"},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1023\/A:1009812409930","volume":"4","author":"B Cabon","year":"1999","unstructured":"Cabon B, de Givry S, Lobjois L, Schiex T, Warners J (1999) Radio link frequency assignment. Constraints 4:79\u201389","journal-title":"Constraints"},{"key":"7_CR19","volume-title":"Markov random fields: theory and applications","author":"R Chellappa","year":"1993","unstructured":"Chellappa R, Jain A (1993) Markov random fields: theory and applications. Academic Press, London"},{"issue":"3","key":"7_CR20","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0165-0114(02)00134-3","volume":"134","author":"M Cooper","year":"2003","unstructured":"Cooper M (2003) Reduction operations in fuzzy or valued constraint satisfaction. Fuzzy Sets Syst 134(3):311\u2013342","journal-title":"Fuzzy Sets Syst"},{"key":"7_CR21","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10601-005-2240-3","volume":"10","author":"M Cooper","year":"2005","unstructured":"Cooper M (2005) High-order consistency in valued constraint satisfaction. Constraints 10:283\u2013305","journal-title":"Constraints"},{"key":"7_CR22","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.artint.2003.09.002","volume":"154","author":"M Cooper","year":"2004","unstructured":"Cooper M, Schiex T (2004) Arc consistency for soft constraints. Artif Intell 154:199\u2013227","journal-title":"Artif Intell"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Cooper M, Cussat-Blanc S, de Roquemaurel M, R\u00e9gnier P (2006) Soft arc consistency applied to optimal planning. In: Proceedings of CP-06, Nantes, France, pp 680\u2013684","DOI":"10.1007\/11889205_50"},{"key":"7_CR24","unstructured":"Cooper M, de\u00a0Givry S, Schiex T (2007) Optimal soft arc consistency. In: Proceedings of IJCAI-07, Hyderabad, India, pp 68\u201373"},{"key":"7_CR25","unstructured":"Cooper M, de Givry S, Sanchez M, Schiex T, Zytnicki M (2008) Virtual arc consistency for valued CSP. In: Proceedings of AAAI-08, Chicago, IL, pp 253\u2013258"},{"issue":"7","key":"7_CR26","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, S\u00e1nchez M, Schiex T, Zytnicki M, Werner T (2010) Soft arc consistency revisited. Artif Intell 174(7):449\u2013478","journal-title":"Artif Intell"},{"issue":"1","key":"7_CR27","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.artint.2004.04.005","volume":"157","author":"A Darwiche","year":"2004","unstructured":"Darwiche A, Marquis P (2004) Compiling propositional weighted bases. Artif Intell 157(1):81\u2013113","journal-title":"Artif Intell"},{"issue":"10","key":"7_CR28","doi-asserted-by":"publisher","first-page":"2805","DOI":"10.1016\/j.cor.2005.01.012","volume":"33","author":"S de Givry","year":"2006","unstructured":"de Givry S, Jeannin L (2006) A unified framework for partial and hybrid search methods in constraint programming. Comput Oper Res 33(10):2805\u20132833","journal-title":"Comput Oper Res"},{"key":"7_CR29","doi-asserted-by":"crossref","unstructured":"de\u00a0Givry S, Katsirelos G (2017) Clique cuts in weighted constraint satisfaction. In: Proceedings of CP-17, Melbourne, Australia, pp 97\u2013113","DOI":"10.1007\/978-3-319-66158-2_7"},{"key":"7_CR30","unstructured":"de\u00a0Givry S, Zytnicki M, Heras F, Larrosa J (2005) Existential arc consistency: getting closer to full arc consistency in weighted CSPs. In: Proceedings of IJCAI-05, Edinburgh, Scotland, pp 84\u201389"},{"key":"7_CR31","unstructured":"de\u00a0Givry S, Schiex T, Verfaillie G (2006) Exploiting tree decomposition and soft local consistency in weighted CSP. In: Proceedings of AAAI-06, Boston, MA, pp 22\u201327"},{"key":"7_CR32","doi-asserted-by":"crossref","unstructured":"de\u00a0Givry S, Prestwich S, O\u2019Sullivan B (2013) Dead-end elimination for weighted CSP. In: Proceedings of CP-13, Uppsala, Sweden, pp 263\u2013272","DOI":"10.1007\/978-3-642-40627-0_22"},{"key":"7_CR33","doi-asserted-by":"crossref","unstructured":"de\u00a0Givry S, Lee J, Leung K, Shum Y (2014) Solving a judge assignment problem using conjunctions of global cost functions. In: Proceedings of CP-14, Lyon, France, pp 797\u2013812","DOI":"10.1007\/978-3-319-10428-7_57"},{"key":"7_CR34","unstructured":"Dechter R (1997) Mini-buckets: a general scheme for generating approximations in automated reasoning. In: Proceedings of IJCAI-97, pp 1297\u20131303"},{"issue":"1\u20132","key":"7_CR35","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0004-3702(99)00059-4","volume":"113","author":"R Dechter","year":"1999","unstructured":"Dechter R (1999) Bucket elimination: a unifying framework for reasoning. Artif Intell 113(1\u20132):41\u201385","journal-title":"Artif Intell"},{"key":"7_CR36","unstructured":"Dechter R (2003) Constraint Processing. Morgan Kaufmann Publishers, Burlington"},{"issue":"2","key":"7_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/636865.636866","volume":"50","author":"R Dechter","year":"2003","unstructured":"Dechter R, Rish I (2003) Mini-buckets: a general scheme for approximating inference. J ACM 50(2):1\u201361","journal-title":"J ACM"},{"key":"7_CR38","unstructured":"Dibangoye J, Amato C, Buffet O, Charpillet F (2013) Optimally solving Dec-POMDPs as continuous-state MDPs. In: Proceedings of IJCAI-13, Beijing, China, pp 90\u201396"},{"key":"7_CR39","unstructured":"Domshlak C, Rossi F, Venable K, Walsh T (2003) Reasoning about soft constraints and conditional preferences: complexity results and approximation techniques. In: Proceedings of IJCAI-03, Acapulco, Mexico, pp 215\u2013220"},{"key":"7_CR40","doi-asserted-by":"crossref","unstructured":"Dubois D, Prade H (1991) Inference in possibilistic hypergraphs. Uncertainty in Knowledge Bases pp 249\u2013259","DOI":"10.1007\/BFb0028110"},{"issue":"4","key":"7_CR41","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF00132735","volume":"6","author":"D Dubois","year":"1996","unstructured":"Dubois D, Fargier H, Prade H (1996) Possibility theory in constraint satisfaction problems: handling priority, preference and uncertainty. Appl Intell 6(4):287\u2013309","journal-title":"Appl Intell"},{"key":"7_CR42","unstructured":"Ermon S, Gomes C, Sabharwal A, Selman B (2013) Embed and project: discrete sampling with universal hashing. In: Advances in Neural Information Processing Systems, pp 2085\u20132093"},{"key":"7_CR43","doi-asserted-by":"crossref","unstructured":"Fargier H, Lang J (1993) Uncertainty in constraint satisfaction problems: a probabilistic approach. In: Proceedings of ECSQARU \u201993, Grenada, Spain, vol 747, pp 97\u2013104","DOI":"10.1007\/BFb0028188"},{"key":"7_CR44","unstructured":"Fargier H, Marquis P (2007) On valued negation normal form formulas. In: Proceedings of IJCAI-07, Hyderabad, India, pp 360\u2013365"},{"key":"7_CR45","unstructured":"Fargier H, Lang J, Schiex T (1993) Selecting preferred solutions in fuzzy constraint satisfaction problems. In: Proceedings of the 1st European Congress on Fuzzy and Intelligent Technologies"},{"key":"7_CR46","unstructured":"Favier A, Elsen JM, de\u00a0Givry S, Legarra A (2010) Optimal haplotype reconstruction in half-sib families. In: ICLP-10 Workshop on Constraint Based Methods for Bioinformatics, Edinburgh, UK"},{"key":"7_CR47","unstructured":"Favier A, de\u00a0Givry S, Legarra A, Schiex T (2011) Pairwise decomposition for combinatorial optimization in graphical models. In: Proceedings of IJCAI-11, Barcelona, Spain"},{"issue":"2","key":"7_CR48","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1051\/ro\/2013030","volume":"47","author":"M Fontaine","year":"2013","unstructured":"Fontaine M, Loudni S, Boizumault P (2013) Exploiting tree decomposition for guiding neighborhoods exploration for VNS. RAIRO - Oper Res 47(2):91\u2013123","journal-title":"RAIRO - Oper Res"},{"key":"7_CR49","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0004-3702(92)90004-H","volume":"58","author":"E Freuder","year":"1992","unstructured":"Freuder E, Wallace R (1992) Partial constraint satisfaction. Artif Intell 58:21\u201370","journal-title":"Artif Intell"},{"key":"7_CR50","unstructured":"Fujishige S (2005) Submodular functions and optimisation, vol 58, 2nd edn. Annals of Discrete Mathematics. Elsevier, Amsterdam"},{"key":"7_CR51","unstructured":"Ghosh S, Kumar A, Varakantham P (2015) Probabilistic inference based message-passing for resource constrained DCOPs. In: Proceedings of IJCAI-15, Buenos Aires, Argentina, pp 411\u2013417"},{"key":"7_CR52","volume-title":"Graphs, dioids and semirings: new models and algorithms","author":"M Gondran","year":"2008","unstructured":"Gondran M, Minoux M (2008) Graphs, dioids and semirings: new models and algorithms, vol 41. Springer Science & Business Media, Berlin"},{"key":"7_CR53","unstructured":"Gondran M, Minoux M (2009) Graphes et algorithmes. Lavoisier, EDF R&D"},{"key":"7_CR54","unstructured":"Harvey W, Ginsberg M (1995) Limited discrepency search. In: Proceedings of IJCAI-95, Montr\u00e9al, Canada"},{"key":"7_CR55","doi-asserted-by":"crossref","unstructured":"Hurley B, OSullivan B, Allouche D, Katsirelos G, Schiex T, Zytnicki M, de Givry S, (2016) Multi-language evaluation of exact solvers in graphical model discrete optimization. Constraints 21(3):413\u2013434","DOI":"10.1007\/s10601-016-9245-y"},{"key":"7_CR56","doi-asserted-by":"crossref","unstructured":"Jeavons P, Cooper M (1995) Tractable constraints on ordered domains. Artif Intell 79(2):327\u2013339","DOI":"10.1016\/0004-3702(95)00107-7"},{"key":"7_CR57","unstructured":"Jeavons P, Krokhin A, \u017divn\u1ef3 S (2014) The complexity of valued constraint satisfaction. Bull EATCS 2(113):"},{"key":"7_CR58","doi-asserted-by":"crossref","unstructured":"Kappes J, Andres B, Hamprecht F, Schn\u00f6rr C, Nowozin S, Batra D, Kim S, Kausler B, Kr\u00f6ger T, Lellmann J, Komodakis N, Savchynskyy B, Rother C (2015) A comparative study of modern inference techniques for structured discrete energy minimization problems. Int J Comput Vis 115(2):155\u2013184","DOI":"10.1007\/s11263-015-0809-x"},{"key":"7_CR59","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-9540-7","volume-title":"Triangular norms","author":"E Klement","year":"2000","unstructured":"Klement E, Mesiar R, Pap E (2000) Triangular norms. Kluwer Academic Publishers, Dordrecht"},{"issue":"2","key":"7_CR60","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1109\/18.910572","volume":"47","author":"F Kschischang","year":"2001","unstructured":"Kschischang F, Frey B, Loeliger H (2001) Factor graphs and the sum-product algorithm. IEEE Trans Inf Theory 47(2):498\u2013519","journal-title":"IEEE Trans Inf Theory"},{"key":"7_CR61","unstructured":"Kumar A, Zilberstein S (2010) Point-based backup for decentralized POMDPs: complexity and new algorithms. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, pp 1315\u20131322"},{"key":"7_CR62","doi-asserted-by":"crossref","unstructured":"Larrosa J (2000) Boosting search with variable elimination. In: Principles and Practice of Constraint Programming - CP 2000, Singapore, pp 291\u2013305","DOI":"10.1007\/3-540-45349-0_22"},{"key":"7_CR63","unstructured":"Lecoutre C, Sais L, Tabary S, Vidal V (2006) Last conflict based reasoning. In: Proceedings of ECAI-06, Riva del Garda, Italy, pp 133\u2013137"},{"key":"7_CR64","unstructured":"Lee J, Leung K (2009) Towards efficient consistency enforcement for global constraints in weighted constraint satisfaction. In: Proceedings of IJCAI-09, Pasadena, USA"},{"key":"7_CR65","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1613\/jair.3476","volume":"43","author":"J Lee","year":"2012","unstructured":"Lee J, Leung K (2012) Consistency techniques for flow-based projection-safe global cost functions in weighted constraint satisfaction. J Artif Intell Res 43:257\u2013292","journal-title":"J Artif Intell Res"},{"key":"7_CR66","doi-asserted-by":"crossref","unstructured":"Lee Y, Sidford A, Wong S (2015) A faster cutting plane method and its implications for combinatorial and convex optimization. IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). Berkeley, CA, USA, pp 1049\u20131065","DOI":"10.1109\/FOCS.2015.68"},{"issue":"3","key":"7_CR67","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/j.ejor.2006.12.062","volume":"191","author":"S Loudni","year":"2006","unstructured":"Loudni S, Boizumault P (2006) Combining VNS with constraint programming for solving anytime optimization problems. Eur J Oper Res 191(3):705\u2013735","journal-title":"Eur J Oper Res"},{"key":"7_CR68","unstructured":"Maier P, Jain D, Sachenbacher M (2011) Diagnostic hypothesis enumeration vs. probabilistic inference for hierarchical automata models. In: International Workshop on Principles of Diagnosis (DX), Murnau, Germany"},{"key":"7_CR69","unstructured":"Marinescu R, Dechter R (2005) AND\/OR branch-and-bound for graphical models. In: Proceedings of IJCAI-05, Edinburgh, Scotland, pp 224\u2013229"},{"key":"7_CR70","unstructured":"Marinescu R, Dechter R (2007) Best-first AND\/OR search for most probable explanations. In: Proceedings of UAI-07, Vancouver, BC, Canada, pp 259\u2013266"},{"key":"7_CR71","doi-asserted-by":"crossref","unstructured":"Meseguer P, Rossi F, Schiex T (2006) Soft constraints. Elsevier, Amsterdam, pp 281\u2013328. Chap 9, Handbook of Constraint Programming","DOI":"10.1016\/S1574-6526(06)80013-1"},{"key":"7_CR72","doi-asserted-by":"crossref","unstructured":"Mitchell D (2003) Resolution and constraint satisfaction. In: Proceedings of CP-03, Kinsale, Ireland, pp 555\u2013569","DOI":"10.1007\/978-3-540-45193-8_38"},{"key":"7_CR73","doi-asserted-by":"crossref","unstructured":"Neveu B, Trombettoni G, Glover F (2004) ID Walk: a candidate list strategy with a simple diversification device. In: Proceedings of CP-04, Toronto, Canada, pp 423\u2013437","DOI":"10.1007\/978-3-540-30201-8_32"},{"key":"7_CR74","doi-asserted-by":"crossref","unstructured":"Nguyen H, Bessiere C, de Givry S, Schiex T (2017) Triangle-based consistencies for cost function networks. Constraints 22:230\u2013264","DOI":"10.1007\/s10601-016-9250-1"},{"key":"7_CR75","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.endm.2014.11.013","volume":"47","author":"A Ouali","year":"2015","unstructured":"Ouali A, Loudni S, Loukil L, Boizumault P, Lebbah Y (2015) Replicated parallel strategies for decomposition guided VNS. Electron Notes Discret Math 47:93\u2013100","journal-title":"Electron Notes Discret Math"},{"key":"7_CR76","unstructured":"Ouali A, Allouche D, de\u00a0Givry S, Loudni S, Lebbah Y, Eckhardt F, Loukil L (2017) Iterative decomposition guided variable neighborhood search for graphical model energy minimization. In: Proceedings of UAI-17, Sydney, Australia, pp 550\u2013559"},{"key":"7_CR77","unstructured":"Papadopoulos H, Tzanetakis G (2012) Modeling chord and key structure with Markov logic. In: Proceedings International Conference of the Society for Music Information Retrieval (ISMIR), pp 121\u2013126"},{"key":"7_CR78","doi-asserted-by":"crossref","unstructured":"Papadopoulos H, Tzanetakis G (2013) Exploiting structural relationships in audio music signals using Markov logic networks. In: 38th International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Canada, pp 4493\u20134497","DOI":"10.1109\/ICASSP.2013.6637597"},{"key":"7_CR79","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1613\/jair.2151","volume":"29","author":"C Pralet","year":"2007","unstructured":"Pralet C, Verfaillie G, Schiex T (2007) An algebraic graphical model for decision with uncertainties, feasibilities, and utilities. J Artif Intell Res 29:421\u2013489","journal-title":"J Artif Intell Res"},{"issue":"6","key":"7_CR80","first-page":"173","volume":"6","author":"A Rosenfeld","year":"1976","unstructured":"Rosenfeld A, Hummel R, Zucker S (1976) Scene labeling by relaxation operations. IEEE Trans Syst Man Cybern 6(6):173\u2013184","journal-title":"IEEE Trans Syst Man Cybern"},{"issue":"1\u20132","key":"7_CR81","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/s10601-007-9029-5","volume":"13","author":"M S\u00e0nchez","year":"2008","unstructured":"S\u00e0nchez M, de Givry S, Schiex T (2008) Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques. Constraints 13(1\u20132):130\u2013154","journal-title":"Constraints"},{"key":"7_CR82","unstructured":"Sanchez M, Allouche D, de\u00a0Givry S, Schiex T (2009) Russian doll search with tree decomposition. In: Proceedings of IJCAI\u201909, Pasadena, USA"},{"key":"7_CR83","doi-asserted-by":"crossref","unstructured":"Schiex T (1992) Possibilistic constraint satisfaction problems or \u201cHow to handle soft constraints\u00a0?\u201d. In: Proceedings of UAI-92, Stanford, CA, pp 269\u2013275","DOI":"10.1016\/B978-1-4832-8287-9.50041-4"},{"key":"7_CR84","doi-asserted-by":"crossref","unstructured":"Schiex T (2000) Arc consistency for soft constraints. In: Proceedings of CP-00, Singapore, pp 411\u2013424","DOI":"10.1007\/3-540-45349-0_30"},{"key":"7_CR85","unstructured":"Schiex T, Fargier H, Verfaillie G (1995) Valued constraint satisfaction problems: hard and easy problems. In: Proceedings of IJCAI-95, Montr\u00e9al, Canada, pp 631\u2013637"},{"key":"7_CR86","unstructured":"Schlesinger M (1976) Sintaksicheskiy analiz dvumernykh zritelnikh signalov v usloviyakh pomekh (Syntactic analysis of two-dimensional visual signals in noisy conditions). Kibernetika 4:113\u2013130. in Russian"},{"key":"7_CR87","unstructured":"Shafer G, Shenoy P (1988) Local computations in hyper-trees. Working paper 201, School of business, University of Kansas"},{"key":"7_CR88","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1109\/TPAMI.1981.4767144","volume":"3","author":"L Shapiro","year":"1981","unstructured":"Shapiro L, Haralick R (1981) Structural descriptions and inexact matching. IEEE Trans Pattern Anal Mach Intell 3:504\u2013519","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"2","key":"7_CR89","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1093\/bioinformatics\/bts658","volume":"29","author":"M Silberstein","year":"2013","unstructured":"Silberstein M, Weissbrod O, Otten L, Tzemach A, Anisenia A, Shtark O, Tuberg D, Galfrin E, Gannon I, Shalata A, Borochowitz Z, Dechter R, Thompson E, Geiger D (2013) A system for exact and approximate genetic linkage analysis of SNP data in large pedigrees. Bioinformatics 29(2):197\u2013205","journal-title":"Bioinformatics"},{"key":"7_CR90","doi-asserted-by":"crossref","unstructured":"Simoncini D, Allouche D, de Givry S, Delmas C, Barbe S, Schiex T (2015) Guaranteed discrete energy optimization on large protein design problems. J Chem Theory Comput 11(12):5980\u20135989","DOI":"10.1021\/acs.jctc.5b00594"},{"key":"7_CR91","unstructured":"Struss P, Fraracci A, Nyga D (2011) An automated model abstraction operator implemented in the multiple modeling environment MOM. In: 25th International Workshop on Qualitative Reasoning, Barcelona, Spain"},{"key":"7_CR92","doi-asserted-by":"crossref","unstructured":"Terrioux C, Jegou P (2003) Bounded backtracking for the valued constraint satisfaction problems. In: Proceedings of CP-03, Kinsale, Ireland, pp 709\u2013723","DOI":"10.1007\/978-3-540-45193-8_48"},{"key":"7_CR93","doi-asserted-by":"crossref","unstructured":"Thapper J, Zivny S (2013) The complexity of finite-valued CSPs. In: Proceedings of the forty-fifth annual ACM symposium on Theory of computing. ACM, pp 695\u2013704","DOI":"10.1145\/2488608.2488697"},{"issue":"17","key":"7_CR94","doi-asserted-by":"publisher","first-page":"2129","DOI":"10.1093\/bioinformatics\/btt374","volume":"29","author":"S Traor\u00e9","year":"2013","unstructured":"Traor\u00e9 S, Allouche D, Andr\u00e9 I, de Givry S, Katsirelos G, Schiex T, Barbe S (2013) A new framework for computational protein design through cost function network optimization. Bioinformatics 29(17):2129\u20132136","journal-title":"Bioinformatics"},{"key":"7_CR95","unstructured":"Verfaillie G, Lema\u00eetre M, Schiex T (1996) Russian doll search. In: Proceedings of AAAI\u201996, Portland, OR, pp 181\u2013187"},{"key":"7_CR96","doi-asserted-by":"crossref","unstructured":"Werner T (2007) A linear programming approach to max-sum problem: a review. IEEE Trans Pattern Anal Mach Intell 29(7):1165\u20131179","DOI":"10.1109\/TPAMI.2007.1036"},{"key":"7_CR97","unstructured":"Wilson N (2005) Decision diagrams for the computation of semiring valuations. In: Proceedings of IJCAI-05, Edinburgh, Scotland, pp 331\u2013336"},{"issue":"1\u20132","key":"7_CR98","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s10601-007-9033-9","volume":"13","author":"M Zytnicki","year":"2008","unstructured":"Zytnicki M, Gaspin C, Schiex T (2008) DARN! A soft constraint solver for RNA motif localization. Constraints 13(1\u20132):91\u2013109","journal-title":"Constraints"},{"key":"7_CR99","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1613\/jair.2797","volume":"35","author":"M Zytnicki","year":"2009","unstructured":"Zytnicki M, Gaspin C, de Givry S, Schiex T (2009) Bounds arc consistency for weighted CSPs. J Artif Intell Res 35:93\u2013621","journal-title":"J Artif Intell Res"}],"container-title":["A Guided Tour of Artificial Intelligence Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-06167-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,8]],"date-time":"2020-05-08T13:10:17Z","timestamp":1588943417000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-06167-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030061661","9783030061678"],"references-count":99,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-06167-8_7","relation":{},"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"8 May 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}