{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T14:13:19Z","timestamp":1766067199666,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030589417"},{"type":"electronic","value":"9783030589424"}],"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"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","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-58942-4_31","type":"book-chapter","created":{"date-parts":[[2020,9,18]],"date-time":"2020-09-18T06:03:58Z","timestamp":1600409038000},"page":"475-491","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Relaxation-Aware Heuristics for Exact Optimization in Graphical Models"],"prefix":"10.1007","author":[{"given":"Fulya","family":"Tr\u00f6sser","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2242-0458","authenticated-orcid":false,"given":"Simon","family":"de Givry","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3727-6698","authenticated-orcid":false,"given":"George","family":"Katsirelos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,19]]},"reference":[{"issue":"1","key":"31_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-008-0001-1","volume":"1","author":"T Achterberg","year":"2009","unstructured":"Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1\u201341 (2009)","journal-title":"Math. Program. Comput."},{"key":"31_CR2","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., et al.: Computational protein design as an optimization problem. Artif. Intell. 212, 59\u201379 (2014)","journal-title":"Artif. Intell."},{"key":"31_CR3","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). https:\/\/doi.org\/10.1007\/978-3-319-23219-5_2"},{"issue":"1\/2","key":"31_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0004-3702(02)00210-2","volume":"140","author":"F Bacchus","year":"2002","unstructured":"Bacchus, F., Chen, X., van Beek, P., Walsh, T.: Binary vs. non-binary constraints. Artif. Intell. 140(1\/2), 1\u201337 (2002)","journal-title":"Artif. Intell."},{"key":"31_CR5","unstructured":"Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: Proceedings of ECAI 2004, pp. 146\u2013150, Valencia (2004)"},{"issue":"7\u20138","key":"31_CR6","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.: Soft arc consistency revisited. Artif. Intell. 174(7\u20138), 449\u2013478 (2010)","journal-title":"Artif. Intell."},{"issue":"1","key":"31_CR7","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10107-004-0518-7","volume":"102","author":"E Danna","year":"2005","unstructured":"Danna, E., Rothberg, E., Le Pape, C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102(1), 71\u201390 (2005)","journal-title":"Math. Program."},{"key":"31_CR8","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). https:\/\/doi.org\/10.1007\/978-3-642-23786-7_19"},{"key":"31_CR9","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, pp. 84\u201389, Edinburgh (2005)"},{"key":"31_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-319-98334-9_7","volume-title":"Principles and Practice of Constraint Programming","author":"E Demirovi\u0107","year":"2018","unstructured":"Demirovi\u0107, E., Chu, G., Stuckey, P.J.: Solution-based phase saving for CP: a value-selection heuristic to simulate local search behavior in complete solvers. In: Hooker, J. (ed.) CP 2018. LNCS, vol. 11008, pp. 99\u2013108. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-98334-9_7"},{"key":"31_CR11","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"31_CR12","unstructured":"Freuder, E.C.: Eliminating interchangeable values in constraint satisfaction problems. In: Proceedings of AAAI 1991, pp. 227\u2013233, Anaheim (1991)"},{"key":"31_CR13","doi-asserted-by":"crossref","unstructured":"Haller, S., Swoboda, P., Savchynskyy, B.: Exact map-inference by confining combinatorial search with LP relaxation. In: Proceedings of AAAI 2018, pp. 6581\u20136588, New Orleans (2018)","DOI":"10.1609\/aaai.v32i1.12202"},{"key":"31_CR14","unstructured":"Heras, F., Larrosa, J.: New inference rules for efficient max-SAT solving. In: Proceedings of the National Conference on Artificial Intelligence, AAAI-2006 (2006)"},{"issue":"3","key":"31_CR15","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"},{"key":"31_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-319-10404-1_11","volume-title":"Medical Image Computing and Computer-Assisted Intervention \u2013 MICCAI 2014","author":"D Kainmueller","year":"2014","unstructured":"Kainmueller, D., Jug, F., Rother, C., Myers, G.: Active graph matching for automatic joint segmentation and annotation of C. elegans. In: Golland, P., Hata, N., Barillot, C., Hornegger, J., Howe, R. (eds.) MICCAI 2014. LNCS, vol. 8673, pp. 81\u201388. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-10404-1_11"},{"key":"31_CR17","volume-title":"Probabilistic Graphical Models: Principles and Techniques","author":"D Koller","year":"2009","unstructured":"Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. The MIT Press, Cambridge (2009)"},{"issue":"10","key":"31_CR18","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 Trans. Pattern Anal. Mach. Intell. 28(10), 1568\u20131583 (2006)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"18","key":"31_CR19","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., Sais, L., Tabary, S., Vidal, V.: Reasoning from last conflict(s) in constraint programming. Artif. Intell. 173(18), 1592\u20131614 (2009)","journal-title":"Artif. Intell."},{"key":"31_CR20","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0004-3702(92)90007-K","volume":"58","author":"S Minton","year":"1992","unstructured":"Minton, S., Johnston, M., Philips, A., Laird, P.: Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems. Artif. Intell. 58, 160\u2013205 (1992)","journal-title":"Artif. Intell."},{"key":"31_CR21","first-page":"129","volume":"9","author":"A Morgado","year":"2014","unstructured":"Morgado, A., Ignatiev, A., Marques-Silva, J.: MSCG: robust core-guided MaxSAT solving. JSAT 9, 129\u2013134 (2014)","journal-title":"JSAT"},{"issue":"103194","key":"31_CR22","first-page":"22p.","volume":"278","author":"A Ouali","year":"2020","unstructured":"Ouali, A., et al.: Variable neighborhood search for graphical model energy minimization. Artif. Intell. 278(103194), 22p. (2020)","journal-title":"Artif. Intell."},{"key":"31_CR23","unstructured":"Savchynskyy, B., Kappes, J.H., Swoboda, P., Schn\u00f6rr, C.: Global map-optimality by shrinking the combinatorial search area with convex relaxation. In: Proceedings of NIPS 2013, pp. 1950\u20131958, Lake Tahoe (2013)"},{"key":"31_CR24","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, Helsinki (2008)"}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-58942-4_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,19]],"date-time":"2022-11-19T00:59:32Z","timestamp":1668819572000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-58942-4_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030589417","9783030589424"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-58942-4_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"19 September 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vienna","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 September 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cpaior2020.dbai.tuwien.ac.at\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"72","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.08","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.08","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}