Document Open Access Logo

Graphical Models: Queries, Complexity, Algorithms (Tutorial)

Authors Martin C. Cooper , Simon de Givry , Thomas Schiex

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.4.pdf
  • Filesize: 0.62 MB
  • 22 pages

Document Identifiers

Author Details

Martin C. Cooper
  • Université Fédérale de Toulouse, ANITI, IRIT, Toulouse, France
Simon de Givry
  • Université Fédérale de Toulouse, ANITI, INRAE, UR 875, Toulouse, France
Thomas Schiex
  • Université Fédérale de Toulouse, ANITI, INRAE, UR 875, Toulouse, France

Funding

The authors have received funding from the French "Investing for the Future – PIA3" program under the Grant agreement ANR-19-PI3A-000, in the context of the ANITI project.
  • Cooper, Martin C.: Funded by ANR-18-CE40-0011
  • de Givry, Simon: Funded by ANR-16-CE40-0028.
  • Schiex, Thomas: Funded by ANR-16-CE40-0028.

Cite AsGet BibTex

Martin C. Cooper, Simon de Givry, and Thomas Schiex. Graphical Models: Queries, Complexity, Algorithms (Tutorial). In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.STACS.2020.4

Abstract

Graphical models (GMs) define a family of mathematical models aimed at the concise description of multivariate functions using decomposability. We restrict ourselves to functions of discrete variables but try to cover a variety of models that are not always considered as "Graphical Models", ranging from functions with Boolean variables and Boolean co-domain (used in automated reasoning) to functions over finite domain variables and integer or real co-domains (usual in machine learning and statistics). We use a simple algebraic semi-ring based framework for generality, define associated queries, relationships between graphical models, complexity results, and families of algorithms, with their associated guarantees.

Subject Classification

ACM Subject Classification
  • Theory of computation → Discrete optimization
  • Mathematics of computing → Graph algorithms
Keywords
  • Computational complexity
  • tree decomposition
  • graphical models
  • submodularity
  • message passing
  • local consistency
  • artificial intelligence
  • valued constraints
  • optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Srinivas M Aji and Robert J McEliece. The generalized distributive law. IEEE transactions on Information Theory, 46(2):325-343, 2000. Google Scholar
  2. David Allouche, Isabelle André, Sophie Barbe, Jessica Davies, Simon de Givry, George Katsirelos, Barry O'Sullivan, Steve Prestwich, Thomas Schiex, and Seydou Traoré. Computational protein design as an optimization problem. Artificial Intelligence, 212:59-79, 2014. Google Scholar
  3. David Allouche, Christian Bessiere, Patrice Boizumault, Simon De Givry, Patricia Gutierrez, Jimmy HM Lee, Ka Lun Leung, Samir Loudni, Jean-Philippe Métivier, Thomas Schiex, and Yi Wu. Tractability-preserving transformations of global cost functions. Artificial Intelligence, 238:166-189, 2016. Google Scholar
  4. David Allouche, Simon De Givry, George Katsirelos, Thomas Schiex, and Matthias Zytnicki. Anytime hybrid best-first search with tree decomposition for weighted CSP. In Principles and Practice of Constraint Programming, pages 12-29. Springer, 2015. Google Scholar
  5. Albert Atserias, Andrei Bulatov, and Victor Dalmau. On the power of k-consistency. In International Colloquium on Automata, Languages, and Programming, pages 279-290. Springer, 2007. Google Scholar
  6. Albert Atserias, Johannes Klaus Fichte, and Marc Thurley. Clause-learning algorithms with many restarts and bounded-width resolution. Journal of Artificial Intelligence Research, 40:353-373, 2011. Google Scholar
  7. Fahiem Bacchus and Adam Grove. Graphical models for preference and utility. In Proceedings of the Eleventh conference on Uncertainty in artificial intelligence, pages 3-10. Morgan Kaufmann Publishers Inc., 1995. Google Scholar
  8. Philippe Baptiste, Claude Le Pape, and Wim Nuijten. Constraint-based scheduling: applying constraint programming to scheduling problems, volume 39. Springer Science & Business Media, 2012. Google Scholar
  9. Roberto Bayardo and Daniel Miranker. On the space-time trade-off in solving constraint satisfaction problems. In Proc. of the 14^th IJCAI, pages 558-562, Montréal, Canada, 1995. Google Scholar
  10. Claude Berrou, Alain Glavieux, and Punya Thitimajshima. Near shannon limit error-correcting coding and decoding: Turbo-codes. 1. In Proceedings of ICC'93-IEEE International Conference on Communications, volume 2, pages 1064-1070. IEEE, 1993. Google Scholar
  11. Umberto Bertelé and Francesco Brioshi. Nonserial Dynamic Programming. Academic Press, 1972. Google Scholar
  12. C. Bessière and J-C. Régin. Refining the basic constraint propagation algorithm. In Proc. IJCAI'2001, pages 309-315, 2001. Google Scholar
  13. Christian Bessière. Arc-consistency and arc-consistency again. Artificial Intelligence, 65:179-190, 1994. Google Scholar
  14. Armin Biere, Marijn Heule, and Hans van Maaren, editors. Handbook of Satisfiability, volume 185. IOS press, 2009. Google Scholar
  15. Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh. Conflict-driven clause learning sat solvers. Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, pages 131-153, 2009. Google Scholar
  16. Christopher M Bishop. Pattern Recognition and Machine Learning. Springer, 2006. Google Scholar
  17. Stefano Bistarelli, Ugo Montanari, and Francesca Rossi. Semiring-based constraint satisfaction and optimization. Journal of the ACM (JACM), 44(2):201-236, 1997. Google Scholar
  18. H L Bodlaender and A M C A Koster. Treewidth Computations I. Upper Bounds. Technical Report UU-CS-2008-032, Utrecht University, Department of Information and Computing Sciences, Utrecht, The Netherlands, September 2008. URL: http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-032.pdf.
  19. Hans L Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical computer science, 209(1-2):1-45, 1998. Google Scholar
  20. E. Boros and P. Hammer. Pseudo-Boolean Optimization. Discrete Appl. Math., 123:155-225, 2002. Google Scholar
  21. Frédéric Boussemart, Fred Hemery, Christophe Lecoutre, and Lakhdar Sais. Boosting systematic search by weighting constraints. In ECAI, volume 16, page 146, 2004. Google Scholar
  22. Andrei A. Bulatov. A dichotomy theorem for nonuniform csps. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319-330. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  23. Andrei A. Bulatov. A short story of the CSP dichotomy conjecture. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019, page 1. IEEE, 2019. URL: https://doi.org/10.1109/LICS.2019.8785678.
  24. mit Çatalyürek and Cevdet Aykanat. Patoh (partitioning tool for hypergraphs). Encyclopedia of Parallel Computing, pages 1479-1487, 2011. Google Scholar
  25. Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. Subquadratic submodular function minimization. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1220-1231. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055419.
  26. Supratik Chakraborty, Kuldeep S Meel, and Moshe Y Vardi. A scalable approximate model counter. In International Conference on Principles and Practice of Constraint Programming, pages 200-216. Springer, 2013. Google Scholar
  27. Edmund Clarke, Orna Grumberg, Somesh Jha, Yuan Lu, and Helmut Veith. Counterexample-guided abstraction refinement. In International Conference on Computer Aided Verification, pages 154-169. Springer, 2000. Google Scholar
  28. David A. Cohen, Martin C. Cooper, and Peter Jeavons. Generalising submodularity and horn clauses: Tractable optimization problems defined by tournament pair multimorphisms. Theor. Comput. Sci., 401(1-3):36-51, 2008. URL: https://doi.org/10.1016/j.tcs.2008.03.015.
  29. M. Cooper, S. de Givry, M. Sanchez, T. Schiex, M. Zytnicki, and T. Werner. Soft arc consistency revisited. Artificial Intelligence, 174:449-478, 2010. Google Scholar
  30. M C. Cooper. An optimal k-consistency algorithm. Artificial Intelligence, 41:89-95, 1989. Google Scholar
  31. M C. Cooper. High-order consistency in Valued Constraint Satisfaction. Constraints, 10:283-305, 2005. Google Scholar
  32. M C. Cooper, S. de Givry, and T. Schiex. Optimal soft arc consistency. In Proc. of IJCAI'2007, pages 68-73, Hyderabad, India, January 2007. Google Scholar
  33. Martin Cooper and Thomas Schiex. Arc consistency for soft constraints. Artificial Intelligence, 154(1-2):199-227, 2004. Google Scholar
  34. Martin C Cooper, Simon de Givry, Martí Sánchez, Thomas Schiex, and Matthias Zytnicki. Virtual Arc Consistency for Weighted CSP. In AAAI, volume 8, pages 253-258, 2008. Google Scholar
  35. Martin C. Cooper and Stanislav Zivny. Hybrid tractability of valued constraint problems. Artif. Intell., 175(9-10):1555-1569, 2011. URL: https://doi.org/10.1016/j.artint.2011.02.003.
  36. Martin C. Cooper and Stanislav Zivny. Hybrid tractable classes of constraint problems. In Andrei A. Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 113-135. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.4.
  37. Adnan Darwiche. Recursive conditioning. Artificial Intelligence, 126(1-2):5-41, 2001. Google Scholar
  38. Adnan Darwiche and Pierre Marquis. Compiling propositional weighted bases. Artificial Intelligence, 157(1-2):81-113, 2004. Google Scholar
  39. Martin Davis, George Logemann, and Donald Loveland. A machine program for theorem-proving. Communications of the ACM, 5(7):394-397, 1962. Google Scholar
  40. Martin Davis and Hilary Putnam. A computing procedure for quantification theory. Journal of the ACM (JACM), 7(3):201-215, 1960. Google Scholar
  41. S. de Givry, T. Schiex, and G. Verfaillie. Exploiting Tree Decomposition and Soft Local Consistency in Weighted CSP. In Proc. of the National Conference on Artificial Intelligence, AAAI-2006, pages 22-27, 2006. Google Scholar
  42. Rina Dechter. Learning while searching in constraint satisfaction problems. In Proc. of AAAI'86, pages 178-183, Philadelphia, PA, 1986. Google Scholar
  43. Rina Dechter. Mini-buckets: A general scheme for generating approximations in automated reasoning. In IJCAI, pages 1297-1303, 1997. Google Scholar
  44. Rina Dechter. Bucket elimination: A unifying framework for reasoning. Artificial Intelligence, 113(1-2):41-85, 1999. Google Scholar
  45. Rina Dechter and Irina Rish. Directional resolution: The Davis-Putnam procedure, revisited. KR, 94:134-145, 1994. Google Scholar
  46. Rina Dechter and Irina Rish. Mini-buckets: A general scheme for bounded inference. Journal of the ACM (JACM), 50(2):107-153, 2003. Google Scholar
  47. C. Domshlak, F. Rossi, KB Venable, and T. Walsh. Reasoning about soft constraints and conditional preferences: complexity results and approximation techniques. In Proc. of the 18^th IJCAI, pages 215-220, Acapulco, Mexico, 2003. Google Scholar
  48. Didier Dubois, Hélene Fargier, and Henri Prade. The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction. In Second IEEE International Conference on Fuzzy Systems, pages 1131-1136. IEEE, 1993. Google Scholar
  49. Didier Dubois, Hélène Fargier, and Henri Prade. Propagation and satisfaction of fuzzy constraints. In Yager R.R. and Zadeh L.A., editors, Fuzzy Sets, Neural Networks and Soft Computing, pages 166-187. Kluwer Acad., 1993. Google Scholar
  50. Stefano Ermon, Carla Gomes, Ashish Sabharwal, and Bart Selman. Taming the curse of dimensionality: Discrete integration by hashing and optimization. In International Conference on Machine Learning, pages 334-342, 2013. Google Scholar
  51. Hélene Fargier, Pierre Marquis, Alexandre Niveau, and Nicolas Schmidt. A knowledge compilation map for ordered real-valued decision diagrams. In Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014. Google Scholar
  52. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57-104, 1998. URL: https://doi.org/10.1137/S0097539794266766.
  53. Eugene C. Freuder and Michael J. Quinn. Taking advantage of stable sets of variables in constraint satisfaction problems. In Proc. of the 9^th IJCAI, pages 1076-1078, Los Angeles, CA, 1985. Google Scholar
  54. Alan George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2):345-363, 1973. Google Scholar
  55. M. Gondran and M. Minoux. Graphes et algorithmes. Lavoisier, EDF R&D, 2009. Google Scholar
  56. Michel Gondran and Michel Minoux. Graphs, dioids and semirings: new models and algorithms, volume 41. Springer Science & Business Media, 2008. Google Scholar
  57. Stefan Haller, Paul Swoboda, and Bogdan Savchynskyy. Exact map-inference by confining combinatorial search with lp relaxation. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018. Google Scholar
  58. Marijn JH Heule and Oliver Kullmann. The science of brute force. Commun. ACM, 60(8):70-79, 2017. Google Scholar
  59. Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, and Stanislav Zivny. A tractable class of binary VCSPs via M-convex intersection. ACM Trans. Algorithms, 15(3):44:1-44:41, 2019. URL: https://doi.org/10.1145/3329862.
  60. Barry Hurley, Barry O’Sullivan, David Allouche, George Katsirelos, Thomas Schiex, Matthias Zytnicki, and Simon de Givry. Multi-language evaluation of exact solvers in graphical model discrete optimization. Constraints, pages 1-22, 2016. Google Scholar
  61. Peter Jeavons and Martin C. Cooper. Tractable constraints on ordered domains. Artif. Intell., 79(2):327-339, 1995. URL: https://doi.org/10.1016/0004-3702(95)00107-7.
  62. Peter Jeavons and Justyna Petke. Local consistency and SAT-solvers. Journal of Artificial Intelligence Research, 43:329-351, 2012. Google Scholar
  63. Philippe Jégou, Hanan Kanso, and Cyril Terrioux. Towards a dynamic decomposition of CSPs with separators of bounded size. In International Conference on Principles and Practice of Constraint Programming, pages 298-315. Springer, 2016. Google Scholar
  64. Philippe Jégou, Hélène Kanso, and Cyril Terrioux. On the relevance of optimal tree decompositions for constraint networks. In 2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI), pages 738-743. IEEE, 2018. Google Scholar
  65. Philippe Jégou, Samba Ndojh Ndiaye, and Cyril Terrioux. A new evaluation of forward checking and its consequences on efficiency of tools for decomposition of CSPs. In 2008 20th IEEE International Conference on Tools with Artificial Intelligence, volume 1, pages 486-490. IEEE, 2008. Google Scholar
  66. Philippe Jégou and Cyril Terrioux. Hybrid backtracking bounded by tree-decomposition of constraint networks. Artificial Intelligence, 146(1):43-75, 2003. Google Scholar
  67. Philippe Jégou and Cyril Terrioux. Decomposition and good recording for solving Max-CSPs. In Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, pages 196-200, 2004. Google Scholar
  68. Joerg Kappes, Bjoern Andres, Fred Hamprecht, Christoph Schnorr, Sebastian Nowozin, Dhruv Batra, Sungwoong Kim, Bernhard Kausler, Jan Lellmann, Nikos Komodakis, et al. A comparative study of modern inference techniques for discrete energy minimization problems. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1328-1335, 2013. Google Scholar
  69. George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1):359-392, 1998. Google Scholar
  70. Kalev Kask, Andrew Gelfand, Lars Otten, and Rina Dechter. Pushing the power of stochastic greedy ordering schemes for inference in graphical models. In Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011. Google Scholar
  71. Ross Kindermann. Markov random fields and their applications. American Mathematical Society, 1980. Google Scholar
  72. E.P. Klement, R. Mesiar, and E. Pap. Triangular Norms. Kluwer Academic Publishers, 2000. Google Scholar
  73. Juerg Kohlas and Nic Wilson. Semiring induced valuation algebras: Exact and approximate local computation algorithms. Artificial Intelligence, 172(11):1360-1399, 2008. Google Scholar
  74. Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009. Google Scholar
  75. Vladimir Kolmogorov. Convergent tree-reweighted message passing for energy minimization. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 28(10):1568-1583, 2006. Google Scholar
  76. Vladimir Kolmogorov and Ramin Zabih. What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis & Machine Intelligence, 2:147-159, 2004. Google Scholar
  77. V.K. Koval and M.I. Schlesinger. Dvumernoe programmirovanie v zadachakh analiza izobrazheniy (two-dimensional programming in image analysis problems),. USSR Academy of Science, Automatics and Telemechanics, 8:149-168, 1976. Google Scholar
  78. Andrei A. Krokhin and Stanislav Zivny. The complexity of valued CSPs. In Andrei A. Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 233-266. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.9.
  79. Jean-Marie Lagniez and Pierre Marquis. An improved decision-DNNF compiler. In IJCAI, pages 667-673, 2017. Google Scholar
  80. J. Larrosa, S. de Givry, F. Heras, and M. Zytnicki. Existential arc consistency: getting closer to full arc consistency in weighted CSPs. In Proc. of the 19^th IJCAI, pages 84-89, Edinburgh, Scotland, August 2005. Google Scholar
  81. Jimmy Ho-Man Lee and Ka Lun Leung. Consistency techniques for flow-based projection-safe global cost functions in weighted constraint satisfaction. Journal of Artificial Intelligence Research, 43(1):257-292, 2012. Google Scholar
  82. Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1049-1065. IEEE, 2015. Google Scholar
  83. Stan Z Li. Markov random field modeling in image analysis. Springer Science & Business Media, 2009. Google Scholar
  84. R. Marinescu and R. Dechter. AND/OR branch-and-bound for graphical models. In Proc. of the 19^th IJCAI, page 224, Edinburgh, Scotland, 2005. Google Scholar
  85. Radu Marinescu and Rina Dechter. Memory intensive branch-and-bound search for graphical models. In Proc. of AAAI'06, page 1200. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006. Google Scholar
  86. Radu Marinescu and Rina Dechter. And/or branch-and-bound search for combinatorial optimization in graphical models. Artificial Intelligence, 173(16-17):1457-1491, 2009. Google Scholar
  87. Radu Marinescu and Rina Dechter. Memory intensive and/or search for combinatorial optimization in graphical models. Artificial Intelligence, 173(16-17):1492-1524, 2009. Google Scholar
  88. P. Meseguer, F. Rossi, and T. Schiex. Soft constraints processing. In F. Rossi, P. van Beek, and T. Walsh, editors, Handbook of Constraint Programming, chapter 9. Elsevier, 2006. Google Scholar
  89. R. Mohr and T.C. Henderson. Arc and path consistency revisited. Artificial Intelligence, 28(2):225-233, 1986. Google Scholar
  90. Matthew W Moskewicz, Conor F Madigan, Ying Zhao, Lintao Zhang, and Sharad Malik. Chaff: Engineering an efficient sat solver. In Proceedings of the 38th annual Design Automation Conference, pages 530-535. ACM, 2001. Google Scholar
  91. Kazuo Murota. Discrete Convex Analysis. SIAM, 2003. Google Scholar
  92. Jaroslav Nešetřil and Patrice Ossona De Mendez. Tree-depth, subgraph coloring and homomorphism bounds. European Journal of Combinatorics, 27(6):1022-1041, 2006. Google Scholar
  93. Hiroki Noguchi, Christine Addy, David Simoncini, Staf Wouters, Bram Mylemans, Luc Van Meervelt, Thomas Schiex, Kam YJ Zhang, Jeremy RH Tame, and Arnout RD Voet. Computational design of symmetrical eight-bladed β-propeller proteins. IUCrJ, 6(1), 2019. Google Scholar
  94. Abdelkader Ouali, David Allouche, Simon de Givry, Samir Loudni, Yahia Lebbah, Lakhdar Loukil, and Patrice Boizumault. Variable neighborhood search for graphical model energy minimization. Artificial Intelligence, 278:103194, 2020. URL: https://doi.org/10.1016/j.artint.2019.103194.
  95. Youngsuk Park, David Hallac, Stephen Boyd, and Jure Leskovec. Learning the network structure of heterogeneous data via pairwise exponential Markov random fields. Proceedings of machine learning research, 54:1302, 2017. Google Scholar
  96. Judea Pearl. Probabilistic Reasoning in Intelligent Systems, Networks of Plausible Inference. Morgan Kaufmann, Palo Alto, 1988. Google Scholar
  97. Daniel Prusa and Tomas Werner. Universality of the local marginal polytope. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1738-1743, 2013. Google Scholar
  98. Neil Robertson and Paul D. Seymour. Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory, Ser. B, 52(2):153-190, 1991. URL: https://doi.org/10.1016/0095-8956(91)90061-N.
  99. J. Alan Robinson. A machine-oriented logic based on the resolution principle. Journal of the ACM, 12:23-44, 1965. Google Scholar
  100. D.J. Rose. Tringulated graphs and the elimination process. Journal of Mathematical Analysis and its Applications, 32, 1970. Google Scholar
  101. F. Rossi, P. van Beek, and T. Walsh, editors. Handbook of Constraint Programming. Elsevier, 2006. Google Scholar
  102. M. Sanchez, D. Allouche, S. de Givry, and T. Schiex. Russian doll search with tree decomposition. In Proc. IJCAI'09, pages 603-608, San Diego (CA), USA, 2009. Google Scholar
  103. T. Schiex. Arc consistency for soft constraints. In Principles and Practice of Constraint Programming - CP 2000, volume 1894 of LNCS, pages 411-424, Singapore, September 2000. Google Scholar
  104. T. Schiex, H. Fargier, and G. Verfaillie. Valued constraint satisfaction problems: hard and easy problems. In Proc. of the 14^th IJCAI, pages 631-637, Montréal, Canada, August 1995. Google Scholar
  105. Thomas Schiex. A note on csp graph parameters. Technical report, Citeseer, 1999. Google Scholar
  106. Thomas Schiex and Gérard Verfaillie. Nogood recording for static and dynamic constraint satisfaction problems. International Journal on Artificial Intelligence Tools, 3(02):187-207, 1994. Google Scholar
  107. D. Schlesinger. Exact Solution of Permuted Submodular MinSum Problems. In Energy Minimization Methods in Computer Vision and Pattern Recognition, number 4679/2007 in LNCS, pages 28-38, August 2007. Google Scholar
  108. Dmitrij Schlesinger. Exact solution of permuted submodular minsum problems. In International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, pages 28-38. Springer, 2007. Google Scholar
  109. M.I. Schlesinger. Sintaksicheskiy analiz dvumernykh zritelnikh signalov v usloviyakh pomekh (Syntactic analysis of two-dimensional visual signals in noisy conditions). Kibernetika, 4:113-130, 1976. Google Scholar
  110. G. Shafer. An axiomatic study of computation in hypertrees. Working paper 232, University of Kansas, School of Business, Lawrence, 1991. Google Scholar
  111. David Simoncini, David Allouche, Simon de Givry, Céline Delmas, Sophie Barbe, and Thomas Schiex. Guaranteed discrete energy optimization on large protein design problems. Journal of Chemical Theory and Computation, 11(12):5980-5989, 2015. URL: https://doi.org/10.1021/acs.jctc.5b00594.
  112. C. Terrioux and P. Jegou. Bounded backtracking for the valued constraint satisfaction problems. In Proc. of the Ninth International Conference on Principles and Practice of Constraint Programming (CP-2003), 2003. Google Scholar
  113. Johan Thapper and Stanislav Zivny. The complexity of finite-valued CSPs. J. ACM, 63(4):37:1-37:33, 2016. URL: https://doi.org/10.1145/2974019.
  114. Peter Van Beek and Xinguang Chen. Cplan: A constraint programming approach to planning. In AAAI/IAAI, pages 585-590, 1999. Google Scholar
  115. Martin Wainwright, Tommi Jaakkola, and Alan Willsky. Tree-based reparameterization analysis of belief propagation and related algorithms for approximate inference on graphs with cycles. In Proceedings IEEE International Symposium on Information Theory, page 113. IEEE, 2002. Google Scholar
  116. T. Werner. A Linear Programming Approach to Max-sum Problem: A Review. IEEE Trans. on Pattern Recognition and Machine Intelligence, 29(7):1165-1179, July 2007. URL: https://doi.org/10.1109/TPAMI.2007.1036.
  117. Jonathan S Yedidia, William T Freeman, and Yair Weiss. Bethe free energy, Kikuchi approximations, and belief propagation algorithms. Advances in neural information processing systems, 13, 2001. Google Scholar
  118. Yuanlin Zhang and Roland HC Yap. Making AC-3 an optimal algorithm. In IJCAI, volume 1, pages 316-321, 2001. Google Scholar
  119. Dmitriy Zhuk. A proof of CSP dichotomy conjecture. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 331-342. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.38.
  120. Stanislav Živny and Peter G Jeavons. Classes of submodular constraints expressible by graph cuts. Constraints, 15(3):430-452, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact