{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:21:43Z","timestamp":1780633303946,"version":"3.54.1"},"reference-count":65,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T00:00:00Z","timestamp":1684195200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T00:00:00Z","timestamp":1684195200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100007655","name":"\u010cesk\u00e9 Vysok\u00e9 U\u010den\u00ed Technick\u00e9 v Praze","doi-asserted-by":"publisher","award":["SGS19\/170\/OHK3\/3T\/13"],"award-info":[{"award-number":["SGS19\/170\/OHK3\/3T\/13"]}],"id":[{"id":"10.13039\/100007655","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007655","name":"\u010cesk\u00e9 Vysok\u00e9 U\u010den\u00ed Technick\u00e9 v Praze","doi-asserted-by":"publisher","award":["SGS22\/061\/OHK3\/1T\/13"],"award-info":[{"award-number":["SGS22\/061\/OHK3\/1T\/13"]}],"id":[{"id":"10.13039\/100007655","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["19-09967S"],"award-info":[{"award-number":["19-09967S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["19-09967S"],"award-info":[{"award-number":["19-09967S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001823","name":"Ministerstvo \u0160kolstv\u00ed, Ml\u00e1de\u017ee a T\u011blov\u00fdchovy","doi-asserted-by":"publisher","award":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"],"award-info":[{"award-number":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"]}],"id":[{"id":"10.13039\/501100001823","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001823","name":"Ministerstvo \u0160kolstv\u00ed, Ml\u00e1de\u017ee a T\u011blov\u00fdchovy","doi-asserted-by":"publisher","award":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"],"award-info":[{"award-number":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"]}],"id":[{"id":"10.13039\/501100001823","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-P3IA-0004"],"award-info":[{"award-number":["ANR-19-P3IA-0004"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007655","name":"Czech Technical University in Prague","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007655","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The notion of reparametrizations of Weighted CSPs (WCSPs) (also known as equivalence-preserving transformations of WCSPs) is well-known and finds its use in many algorithms to approximate or bound the optimal WCSP value. In contrast, the concept of super-reparametrizations (which are changes of the weights that keep or increase the WCSP objective for every assignment) was already proposed but never studied in detail. To fill this gap, we present a number of theoretical properties of super-reparametrizations and compare them to those of reparametrizations. Furthermore, we propose a framework for computing upper bounds on the optimal value of the (maximization version of) WCSP using super-reparametrizations. We show that it is in principle possible to employ arbitrary (under some technical conditions) constraint propagation rules to improve the bound. For arc consistency in particular, the method reduces to the known Virtual AC (VAC) algorithm. We implemented the method for singleton arc consistency (SAC) and compared it to other strong local consistencies in WCSPs on a public benchmark. The results show that the bounds obtained from SAC are superior for many instance groups.<\/jats:p>","DOI":"10.1007\/s10601-023-09343-6","type":"journal-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T08:05:42Z","timestamp":1684224342000},"page":"277-319","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Super-reparametrizations of weighted CSPs: properties and optimization perspective"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1944-6569","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Dlask","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6161-7157","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Werner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simon","family":"de Givry","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,5,16]]},"reference":[{"issue":"113\u2013130","key":"9343_CR1","first-page":"2","volume":"4","author":"M Schlesinger","year":"1976","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), 2.","journal-title":"Kibernetika"},{"issue":"7","key":"9343_CR2","doi-asserted-by":"publisher","first-page":"1165","DOI":"10.1109\/TPAMI.2007.1036","volume":"29","author":"T Werner","year":"2007","unstructured":"Werner, T. (2007). A linear programming approach to max-sum problem: A review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(7), 1165\u20131179.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"1\u20132","key":"9343_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000001","volume":"1","author":"MJ Wainwright","year":"2008","unstructured":"Wainwright, M. J., & Jordan, M. I. (2008). Graphical Models, Exponential Families, and Variational Inference. Foundations and Trends in Machine Learning, 1(1\u20132), 1\u2013305.","journal-title":"Foundations and Trends in Machine Learning"},{"key":"9343_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33974-5","volume-title":"The Complexity of Valued Constraint Satisfaction Problems","author":"S \u017divn\u00fd","year":"2012","unstructured":"\u017divn\u00fd, S. (2012). The Complexity of Valued Constraint Satisfaction Problems. Cognitive Technologies: Springer."},{"issue":"3\u20134","key":"9343_CR5","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1561\/0600000084","volume":"11","author":"B Savchynskyy","year":"2019","unstructured":"Savchynskyy, B. (2019). Discrete graphical models - an optimization perspective. Foundations and Trends in Computer Graphics and Vision, 11(3\u20134), 160\u2013429.","journal-title":"Foundations and Trends in Computer Graphics and Vision"},{"issue":"7\u20138","key":"9343_CR6","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1016\/j.artint.2010.02.001","volume":"174","author":"MC Cooper","year":"2010","unstructured":"Cooper, M. C., de Givry, S., Sanchez, M., Schiex, T., Zytnicki, M., & Werner, T. (2010). Soft arc consistency revisited. Artificial Intelligence, 174(7\u20138), 449\u2013478.","journal-title":"Artificial Intelligence"},{"issue":"10","key":"9343_CR7","doi-asserted-by":"publisher","first-page":"1568","DOI":"10.1109\/TPAMI.2006.200","volume":"28","author":"V Kolmogorov","year":"2006","unstructured":"Kolmogorov, V. (2006). Convergent tree-reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10), 1568\u20131583.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"9343_CR8","unstructured":"Globerson, A., Jaakkola, T.S. (2008). Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. In Advances in neural information processing systems (pp 553\u2013560)"},{"key":"9343_CR9","doi-asserted-by":"crossref","unstructured":"Tourani, S., Shekhovtsov, A., Rother, C., Savchynskyy, B. (2018). MPLP++: Fast, parallel dual block-coordinate ascent for dense graphical models. In Proceedings of the European conference on computer vision (pp. 251\u2013267)","DOI":"10.1007\/978-3-030-01225-0_16"},{"key":"9343_CR10","unstructured":"Tourani, S., Shekhovtsov, A., Rother, C., Savchynskyy, B. (2020) Taxonomy of dual block-coordinate ascent methods for discrete energy minimization. In International conference on artificial intelligence and statistics (pp 2775\u20132785). PMLR"},{"issue":"8","key":"9343_CR11","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1109\/TPAMI.2009.134","volume":"32","author":"T Werner","year":"2010","unstructured":"Werner, T. (2010). Revisiting the linear programming relaxation approach to gibbs energy minimization and weighted constraint satisfaction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(8), 1474\u20131488.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"5","key":"9343_CR12","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1109\/TPAMI.2014.2363465","volume":"37","author":"V Kolmogorov","year":"2014","unstructured":"Kolmogorov, V. (2014). A new look at reweighted message passing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(5), 919\u2013930.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"9343_CR13","doi-asserted-by":"crossref","unstructured":"Werner, T., Pr\u016f\u0161a, D., Dlask, T. (2020). Relative interior rule in block-coordinate descent. In Proceedings of the IEEE\/CVF conference on computer vision and pattern recognition (pp. 7559\u20137567)","DOI":"10.1109\/CVPR42600.2020.00758"},{"key":"9343_CR14","unstructured":"de Givry, S., Heras, F., Zytnicki, M., Larrosa, J. (2005). Existential arc consistency: Getting closer to full arc consistency in weighted CSPs. In IJCAI (vol. 5, pp. 84\u201389)"},{"key":"9343_CR15","unstructured":"Cooper, M.C., de\u00a0Givry, S., Sanchez, M., Schiex, T., Zytnicki, M. (2008). Virtual arc consistency for weighted CSP. In Proceedings of the 22nd AAAI conference on artificial intelligence (pp. 253\u2013258)"},{"key":"9343_CR16","first-page":"149","volume":"8","author":"VK Koval","year":"1976","unstructured":"Koval, V. K., & Schlesinger, M. I. (1976). Dvumernoe programmirovanie v zadachakh analiza izobrazheniy (Two-dimensional Programming in Image Analysis Problems). Automatics and Telemechanics, 8, 149\u2013168. In Russian.","journal-title":"Automatics and Telemechanics"},{"key":"9343_CR17","unstructured":"Werner, T. (2005). A Linear Programming Approach to Max-sum Problem: A Review. Center for Machine Perception, Czech Technical University. CTU-CMP-2005-25"},{"key":"9343_CR18","unstructured":"Cooper, M.C., de Givry, S., Schiex, T. (2007). Optimal soft arc consistency. In Proceedings of the 20th international joint conference on artifical intelligence (vol. 7, pp. 68\u201373)"},{"issue":"4","key":"9343_CR19","doi-asserted-by":"publisher","first-page":"898","DOI":"10.1109\/TPAMI.2014.2353626","volume":"37","author":"D Pr\u016f\u0161a","year":"2015","unstructured":"Pr\u016f\u0161a, D., & Werner, T. (2015). Universality of the Local Marginal Polytope. IEEE Trans on Pattern Analysis and Machine Intelligence, 37(4), 898\u2013904.","journal-title":"IEEE Trans on Pattern Analysis and Machine Intelligence"},{"issue":"3","key":"9343_CR20","doi-asserted-by":"publisher","first-page":"1745","DOI":"10.1137\/17M1142922","volume":"29","author":"D Pr\u016f\u0161a","year":"2019","unstructured":"Pr\u016f\u0161a, D., & Werner, T. (2019). Solving LP relaxations of some NP-hard problems is as hard as solving any linear program. SIAM J Optimization, 29(3), 1745\u20131771.","journal-title":"SIAM J Optimization"},{"key":"9343_CR21","unstructured":"Sontag, D., Meltzer, T., Globerson, A., Jaakkola, T., Weiss, Y. Tightening LP Relaxations for MAP using Message Passing. Citeseer"},{"issue":"2","key":"9343_CR22","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/s10601-016-9250-1","volume":"22","author":"H Nguyen","year":"2017","unstructured":"Nguyen, H., Bessiere, C., de Givry, S., & Schiex, T. (2017). Triangle-based consistencies for cost function networks. Constraints, 22(2), 230\u2013264.","journal-title":"Constraints"},{"key":"9343_CR23","unstructured":"Batra, D., Nowozin, S., Kohli, P. (2011). Tighter relaxations for MAP-MRF inference: A local primal-dual gap based separation algorithm. In Proceedings of the Fourteenth international conference on artificial intelligence and statistics (pp. 146\u2013154)"},{"key":"9343_CR24","doi-asserted-by":"crossref","unstructured":"Thapper, J., \u017divn\u00fd, S. (2015). Sherali-Adams relaxations for valued CSPs. In International colloquium on automata, languages, and programming (pp. 1058\u20131069). Springer","DOI":"10.1007\/978-3-662-47672-7_86"},{"key":"9343_CR25","doi-asserted-by":"crossref","unstructured":"Komodakis, N., Paragios, N. (2008) Beyond loose LP-relaxations: Optimizing MRFs by repairing cycles. In European conference on computer vision (pp. 806\u2013820). Springer","DOI":"10.1007\/978-3-540-88690-7_60"},{"issue":"1","key":"9343_CR26","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.artint.2007.09.001","volume":"172","author":"C Bessiere","year":"2008","unstructured":"Bessiere, C., & Debruyne, R. (2008). Theoretical analysis of singleton arc consistency and its extensions. Artificial Intelligence, 172(1), 29\u201341.","journal-title":"Artificial Intelligence"},{"key":"9343_CR27","unstructured":"Sontag, D., Jaakkola, T. (2009). Tree block coordinate descent for MAP in graphical models. In Artificial intelligence and statistics (pp. 544\u2013551)"},{"key":"9343_CR28","unstructured":"Dlask, T., Werner, T., de\u00a0Givry, S. (2021). Bounds on weighted CSPs using constraint propagation and super-reparametrizations. In L.D. Michel, (Eds.) 27th international conference on principles and practice of constraint programming (CP 2021). vol. 210 of Leibniz International Proceedings in Informatics (LIPIcs) (pp. 23:1\u201323:18). Dagstuhl, Germany: Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"4","key":"9343_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2974019","volume":"63","author":"J Thapper","year":"2016","unstructured":"Thapper, J., & \u017divn\u00fd, S. (2016). The complexity of finite-valued CSPs. Journal of the ACM (JACM), 63(4), 1\u201333.","journal-title":"Journal of the ACM (JACM)"},{"issue":"1","key":"9343_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/130945648","volume":"44","author":"V Kolmogorov","year":"2015","unstructured":"Kolmogorov, V., Thapper, J., & \u017divn\u00fd, S. (2015). The power of linear programming for general-valued CSPs. SIAM Journal on Computing, 44(1), 1\u201336.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"9343_CR31","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s11263-015-0809-x","volume":"115","author":"JH Kappes","year":"2015","unstructured":"Kappes, J. H., Andres, B., Hamprecht, F. A., Schn\u00f6rr, C., Nowozin, S., Batra, D., et al. (2015). A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems. Intl. J. of Computer Vision, 115(2), 155\u2013184.","journal-title":"Intl. J. of Computer Vision"},{"key":"9343_CR32","doi-asserted-by":"crossref","unstructured":"Cooper, M.C., de\u00a0Givry, S., Schiex, T. (2020) Valued Constraint Satisfaction Problems. In A guided tour of artificial intelligence research (pp. 185\u2013207). Springer","DOI":"10.1007\/978-3-030-06167-8_7"},{"key":"9343_CR33","doi-asserted-by":"publisher","DOI":"10.1142\/5021","volume-title":"Convex Analysis in General Vector Spaces","author":"C Zalinescu","year":"2002","unstructured":"Zalinescu, C. (2002). Convex Analysis in General Vector Spaces. World Scientific."},{"issue":"1\u20132","key":"9343_CR34","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.artint.2003.06.004","volume":"155","author":"MC Cooper","year":"2004","unstructured":"Cooper, M. C. (2004). Cyclic consistency: a local reduction operation for binary valued constraints. Artificial Intelligence, 155(1\u20132), 69\u201392.","journal-title":"Artificial Intelligence"},{"issue":"2","key":"9343_CR35","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s10957-010-9752-8","volume":"148","author":"J Jahn","year":"2011","unstructured":"Jahn, J., & Ha, T. X. D. (2011). New order relations in set optimization. Journal of Optimization Theory and Applications, 148(2), 209\u2013236.","journal-title":"Journal of Optimization Theory and Applications"},{"key":"9343_CR36","doi-asserted-by":"crossref","unstructured":"Boyd, S., Vandenberghe. L. (2004) Convex optimization. Cambridge university press","DOI":"10.1017\/CBO9780511804441"},{"issue":"7","key":"9343_CR37","doi-asserted-by":"publisher","first-page":"1455","DOI":"10.1109\/TPAMI.2014.2363833","volume":"37","author":"T Werner","year":"2015","unstructured":"Werner, T. (2015). Marginal consistency: upper-bounding partition functions over commutative semirings. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(7), 1455\u20131468.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"9343_CR38","doi-asserted-by":"crossref","unstructured":"Dlask, T., Werner, T. (2020). Bounding linear programs by constraint propagation: application to Max-SAT. In International conference on principles and practice of constraint programming (pp. 177\u2013193). Springer","DOI":"10.1007\/978-3-030-58475-7_11"},{"key":"9343_CR39","doi-asserted-by":"crossref","unstructured":"Gr\u00e9goire, \u00c9., Mazure, B., Piette, C. (2007). MUST: Provide a finer-grained explanation of unsatisfiability. In International conference on principles and practice of constraint programming (pp. 317\u2013331). Springer","DOI":"10.1007\/978-3-540-74970-7_24"},{"issue":"04","key":"9343_CR40","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1142\/S0218213008004138","volume":"17","author":"E Gr\u00e9goire","year":"2008","unstructured":"Gr\u00e9goire, E., Mazure, B., & Piette, C. (2008). On finding minimally unsatisfiable cores of CSPs. International Journal on Artificial Intelligence Tools, 17(04), 745\u2013763.","journal-title":"International Journal on Artificial Intelligence Tools"},{"key":"9343_CR41","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Wolfe, D. (1985) The complexity of facets resolved. Cornell University","DOI":"10.1109\/SFCS.1985.56"},{"key":"9343_CR42","unstructured":"Freuder, E.C., Elfe, C.D. (1996) Neighborhood inverse consistency preprocessing. In AAAI\/IAAI (Vol 1, pp. 202\u2013208)"},{"key":"9343_CR43","doi-asserted-by":"publisher","DOI":"10.1016\/S1574-6526(06)80007-6","volume-title":"Constraint propagation","author":"C Bessiere","year":"2006","unstructured":"Bessiere, C. (2006). Constraint propagation. In Handbook of constraint programming: Elsevier."},{"issue":"1","key":"9343_CR44","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10601-009-9080-5","volume":"16","author":"C Bessiere","year":"2011","unstructured":"Bessiere, C., Cardon, S., Debruyne, R., & Lecoutre, C. (2011). Efficient algorithms for singleton arc consistency. Constraints, 16(1), 25\u201353.","journal-title":"Constraints"},{"key":"9343_CR45","volume-title":"Minimizing Convex Piecewise-Affine Functions by Local Consistency Techniques [Master\u2019s thesis]","author":"T Dlask","year":"2018","unstructured":"Dlask, T. (2018). Minimizing Convex Piecewise-Affine Functions by Local Consistency Techniques [Master\u2019s thesis]. Faculty of Electrical Engineering: Czech Technical University in Prague."},{"issue":"1\u20132","key":"9343_CR46","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2004.05.004","volume":"159","author":"J Larrosa","year":"2004","unstructured":"Larrosa, J., & Schiex, T. (2004). Solving weighted CSP by maintaining arc consistency. Artificial Intelligence, 159(1\u20132), 1\u201326.","journal-title":"Artificial Intelligence"},{"key":"9343_CR47","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B. (1993) Network flows: Theory, applications and algorithms"},{"key":"9343_CR48","doi-asserted-by":"crossref","unstructured":"Dlask, T. (2022). Block-Coordinate Descent and Local Consistencies in Linear Programming [Dissertation, available online: https:\/\/dspace.cvut.cz\/handle\/10467\/102874?locale-attribute=en]. Czech Technical University in Prague, Faculty of Electrical Engineering;","DOI":"10.1007\/s10601-023-09350-7"},{"key":"9343_CR49","first-page":"2000","volume":"1232","author":"KH Rosen","year":"2000","unstructured":"Rosen, K. H., & Michaels, J. G. (2000). Handbook of Discrete and Combinatorial Mathematics. Boca Raton, CRC Press, 1232, 2000.","journal-title":"Boca Raton, CRC Press"},{"key":"9343_CR50","unstructured":"Debruyne, R., Bessiere, C. (1997). Some practicable filtering techniques for the constraint satisfaction problem. In Proceedings of IJCAI\u201997 (pp. 412\u2013417)"},{"key":"9343_CR51","unstructured":"Available online.: toulbar2. https:\/\/miat.inrae.fr\/toulbar2.\u00a0Accessed 12 Jan 2021."},{"key":"9343_CR52","unstructured":"Available online.: Cost Function Library benchmark. https:\/\/forgemia.inra.fr\/thomas.schiex\/cost-function-library.\u00a0Accessed 12 Jan 2021."},{"key":"9343_CR53","unstructured":"Available online.: Spin Glass Server. https:\/\/software.cs.uni-koeln.de\/spinglass, recently moved to http:\/\/spinglass.uni-bonn.de\/.\u00a0Accessed 12 Jan 2023."},{"issue":"1","key":"9343_CR54","doi-asserted-by":"publisher","first-page":"1","DOI":"10.3233\/AIC-2010-0473","volume":"24","author":"MC Cooper","year":"2011","unstructured":"Cooper, M. C., de Roquemaurel, M., & R\u00e9gnier, P. (2011). A weighted CSP approach to cost-optimal planning. AI Communications, 24(1), 1\u201329.","journal-title":"AI Communications"},{"issue":"2","key":"9343_CR55","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s12532-018-0147-4","volume":"11","author":"F Furini","year":"2019","unstructured":"Furini, F., Traversi, E., Belotti, P., Frangioni, A., Gleixner, A., Gould, N., et al. (2019). QPLIB: a library of quadratic programming instances. Mathematical Programming Computation, 11(2), 237\u2013265.","journal-title":"Mathematical Programming Computation"},{"key":"9343_CR56","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U Montanari","year":"1974","unstructured":"Montanari, U. (1974). Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences, 7, 95\u2013132.","journal-title":"Information Sciences"},{"key":"9343_CR57","volume-title":"Constraint processing","author":"R Dechter","year":"2003","unstructured":"Dechter, R., Cohen, D., et al. (2003). Constraint processing. Morgan Kaufmann."},{"key":"9343_CR58","doi-asserted-by":"crossref","unstructured":"Astesana, J., Cosserat, L., Fargier, H. (2010) Constraint-based vehicle configuration: A case study. In 2010 22nd IEEE international conference on tools with artificial intelligence (vol 1, pp 68\u201375)","DOI":"10.1109\/ICTAI.2010.19"},{"key":"9343_CR59","doi-asserted-by":"crossref","unstructured":"Bessiere, C., Fargier, H., Lecoutre, C. (2013). Global inverse consistency for interactive constraint satisfaction. In Schulte, C. (Es), Principles and practice of constraint programming (pp. 159\u2013174). Berlin, Springer","DOI":"10.1007\/978-3-642-40627-0_15"},{"key":"9343_CR60","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809088","volume-title":"Introduction to lattices and order","author":"BA Davey","year":"2002","unstructured":"Davey, B. A., & Priestley, H. A. (2002). Introduction to lattices and order. Cambridge University Press."},{"key":"9343_CR61","volume-title":"Lattices and Ordered Algebraic Structures","author":"TS Blyth","year":"2005","unstructured":"Blyth, T. S. (2005). Lattices and Ordered Algebraic Structures. Springer, London: Universitext."},{"key":"9343_CR62","doi-asserted-by":"crossref","unstructured":"Alsuwaiyel, M. (1999). Algorithms: Design Techniques and Analysis. World Scientific","DOI":"10.1142\/4002"},{"key":"9343_CR63","doi-asserted-by":"crossref","unstructured":"Karp, RM. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85\u2013103). Springer","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"9343_CR64","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.artint.2012.07.006","volume":"191","author":"G Gottlob","year":"2012","unstructured":"Gottlob, G. (2012). On minimal constraint networks. Artificial Intelligence, 191, 42\u201360.","journal-title":"Artificial Intelligence"},{"key":"9343_CR65","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.tcs.2018.06.008","volume":"745","author":"G Escamocher","year":"2018","unstructured":"Escamocher, G., & O\u2019Sullivan, B. (2018). Pushing the frontier of minimality. Theoretical Computer Science, 745, 172\u2013201.","journal-title":"Theoretical Computer Science"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09343-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-023-09343-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09343-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,4]],"date-time":"2023-08-04T02:09:11Z","timestamp":1691114951000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-023-09343-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,16]]},"references-count":65,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["9343"],"URL":"https:\/\/doi.org\/10.1007\/s10601-023-09343-6","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,16]]},"assertion":[{"value":"21 February 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}