R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network flows: Theory, Algorithms and Applications, 2011.

D. Allouche, I. André, S. Barbe, J. Davies, S. De-givry et al., Computational protein design as an optimization problem, Artificial Intelligence, vol.212, pp.59-79, 2014.
DOI : 10.1016/j.artint.2014.03.005

URL : https://hal.archives-ouvertes.fr/hal-01268554

D. Allouche, C. Bessì-ere, P. Boizumault, S. De-givry, P. Gutierrez et al., Tractability and Decompositions of Global Cost Functions, 2015.

D. Allouche, S. De-givry, G. Katsirelos, T. Schiex, and M. Zytnicki, Anytime Hybrid Best-First Search with Tree Decomposition for Weighted CSP, Proc. of CP-15, pp.12-28, 2015.
DOI : 10.1007/978-3-319-23219-5_2

URL : https://hal.archives-ouvertes.fr/hal-01198361

C. Beeri, R. Fagin, D. Maier, and M. Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM, vol.30, issue.3, pp.479-513, 1983.
DOI : 10.1145/2402.322389

N. Beldiceanu, Pruning for the Minimum Constraint Family and for the Number of Distinct Values Constraint Family, Proceedings of CP'01, pp.211-224, 2001.
DOI : 10.1007/3-540-45578-7_15

N. Beldiceanu, M. Carlsson, R. Debruyne, and T. Petit, Reformulation of Global Constraints Based on Constraints Checkers, Constraints, vol.11, issue.2, pp.339-362, 2005.
DOI : 10.1007/s10601-005-2809-x

N. Beldiceanu, M. Carlsson, and J. Rampon, Global Constraint Catalog, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00485396

N. Beldiceanu and E. Contejean, Introducing global constraints in CHIP, Mathematical and Computer Modelling, vol.20, issue.12, pp.97-123, 1994.
DOI : 10.1016/0895-7177(94)90127-9

URL : https://hal.archives-ouvertes.fr/hal-00442810

N. Beldiceanu, I. Katriel, and S. Thiel, Filtering Algorithms for the Same??Constraint, Proceedings of CPAIOR'04, pp.65-79, 2004.
DOI : 10.1007/978-3-540-24664-0_5

C. Bessì-ere, F. Rossi, P. Van-beek, and T. Walsh, Constraint propagation, Handbook of Constraint Programming, pp.29-84, 2006.

C. Bessì-ere, E. Hebrard, B. Hnich, Z. Kiziltan, C. Quimper et al., Reformulating global constraints: the SLIDE and REGULAR constraints. Abstraction, Reformulation, and Approximation, pp.80-92, 2007.

C. Bessì-ere, E. Hebrard, B. Hnich, Z. Kiziltan, and T. Walsh, SLIDE: A Useful Special Case of the CARDPATH Constraint, Proceedings of ECAI'08, pp.475-479, 2008.

C. Bessì-ere and P. Van-hentenryck, To be or not to be ... a global constraint, Proceedings of CP'03, pp.789-794, 2003.

F. Boussemart, F. Hemery, C. Lecoutre, and L. Sais, Boosting Systematic Search by Weighting Constraints, pp.146-150, 2004.

B. Cabon, S. De-givry, L. Lobjois, T. Schiex, and J. Warners, Radio link frequency assignment, Constraints, vol.4, issue.1, pp.79-89, 1999.
DOI : 10.1023/A:1009812409930

M. Cooper and T. Schiex, Arc consistency for soft constraints, Artificial Intelligence, vol.154, issue.1-2, pp.199-227, 2004.
DOI : 10.1016/j.artint.2003.09.002

M. C. Cooper, Reduction operations in fuzzy or valued constraint satisfaction. Fuzzy Sets and Systems, pp.311-342, 2003.

M. C. Cooper, High-Order Consistency in Valued Constraint Satisfaction, Constraints, vol.6, issue.6, pp.283-305, 2005.
DOI : 10.1007/s10601-005-2240-3

G. Cornuéjols and M. Dawande, A Class of Hard Small 0-1 Programs, Proceedings of Integer Programming and Combinatorial Optimization, pp.284-293, 1998.

R. Dechter and I. Rish, Mini-buckets, Journal of the ACM, vol.50, issue.2, pp.107-153, 2003.
DOI : 10.1145/636865.636866

J. Desmet, M. De-maeyer, B. Hazes, and I. Lasters, The dead-end elimination theorem and its use in protein side-chain positioning, Nature, vol.356, issue.6369, pp.539-581, 1992.
DOI : 10.1038/356539a0

J. S. Dibangoye, C. Amato, O. Buffet, and F. Charpillet, Optimally solving dec-pomdps as continuous-state mdps, Proceedings of the Twenty-Third international joint conference on Artificial Intelligence, pp.90-96, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00907338

S. Ermon, C. P. Gomes, A. Sabharwal, and B. Selman, Embed and project: Discrete sampling with universal hashing, Advances in Neural Information Processing Systems, pp.2085-2093, 2013.

A. Favier, S. De-givry, A. Legarra, and T. Schiex, Pairwise decomposition for combinatorial optimization in graphical models, Proc. of IJCAI-11, pp.2126-2132, 2011.

J. Flum and M. Grohe, Parameterized Complexity Theory, 2006.

S. De-givry, F. Heras, M. Zytnicki, and J. Larrosa, Existential Arc Consistency: Getting Closer to Full Arc Consistency in Weighted CSPs, Proceedings of IJCAI'05, pp.84-89, 2005.

S. De-givry, S. Prestwich, and B. O-'sullivan, Dead-End Elimination for Weighted CSP, Proceedings of CP'13, pp.263-272, 2013.
DOI : 10.1007/978-3-642-40627-0_22

W. J. Van-hoeve, G. Pesant, and L. M. Rousseau, On global warming: Flow-based soft global constraints, Journal of Heuristics, vol.1, issue.4, pp.347-373, 2006.
DOI : 10.1007/s10732-006-6550-4

B. Hurley, B. O-'sullivan, D. Allouche, G. Katsirelos, T. Schiex et al., Multi-language evaluation in graphical model optimization. Constraints Initially submitted to CP-AI-OR, 2016.

S. Kadioglu and M. Sellmann, Grammar constraints, Constraints, vol.8, issue.1, pp.117-144, 2010.
DOI : 10.1007/s10601-009-9073-4

G. Katsirelos, N. Narodytska, and T. Walsh, The weighted Grammar constraint, Annals of Operations Research, vol.39, issue.2, pp.179-207, 2011.
DOI : 10.1007/s10479-010-0697-y

M. Krom, The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary, Zeitschrift f??r Mathematische Logik und Grundlagen der Mathematik, vol.24, issue.1-2, pp.15-20, 1967.
DOI : 10.1002/malq.19670130104

J. Larrosa, Boosting Search with Variable Elimination, Proceedings of CP'00, pp.291-305, 2000.
DOI : 10.1007/3-540-45349-0_22

J. Larrosa and T. Schiex, In the Quest of the Best Form of Local Consistency for Weighted CSP, Proceedings of IJCAI'03, pp.239-244, 2003.

J. Larrosa and T. Schiex, Solving weighted CSP by maintaining arc consistency, Artificial Intelligence, vol.159, issue.1-2, pp.1-26, 2004.
DOI : 10.1016/j.artint.2004.05.004

J. L. Lauriere, A language and a program for stating and solving combinatorial problems, Artificial Intelligence, vol.10, issue.1, pp.29-127, 1978.
DOI : 10.1016/0004-3702(78)90029-2

C. Lecoutre, O. Roussel, and D. E. Dehani, WCSP Integration of Soft Neighborhood Substitutability, Proceedings of CP'12, pp.406-421, 2012.
DOI : 10.1007/978-3-642-33558-7_31

URL : https://hal.archives-ouvertes.fr/hal-00866333

C. Lecoutre, L. Sa¨?ssa¨?s, S. Tabary, and V. Vidal, Reasoning from last conflict(s) in constraint programming, Artificial Intelligence, vol.173, issue.18, p.15921614, 2009.
DOI : 10.1016/j.artint.2009.09.002

URL : https://hal.archives-ouvertes.fr/hal-00868108

J. H. Lee and K. L. Leung, Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction, Proceedings of IJCAI'09, pp.559-565, 2009.

J. H. Lee and K. L. Leung, A Stronger Consistency for Soft Global Constraints in Weighted Constraint Satisfaction, Proceedings of AAAI'10, pp.121-127, 2010.

J. H. Lee and K. L. Leung, Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction, Journal of Artificial Intelligence Research, vol.43, pp.257-292, 2012.

J. H. Lee, K. L. Leung, and Y. Wu, Polynomially Decomposable Global Cost Functions in Weighted Constraint Satisfaction, Proceedings of AAAI'12, pp.507-513, 2012.

J. H. Lee and Y. W. Shum, Modeling Soft Global Constraints as Linear Programs in Weighted Constraint Satisfaction, 2011 IEEE 23rd International Conference on Tools with Artificial Intelligence, pp.305-312, 2011.
DOI : 10.1109/ICTAI.2011.53

A. Oplobedu, J. Marcovitch, and Y. Tourbier, CHARME: Un langage industriel de programmation par contraintes, illustré par une application chez Renault, Proceedings of the Ninth International Workshop on Expert Systems and their Applications: General Conference, pp.55-70, 1989.

C. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, Journal of Computer and System Sciences, vol.43, issue.3, pp.425-440, 1991.
DOI : 10.1016/0022-0000(91)90023-X

B. Parrello, W. Kabat, and L. Wos, Job-shop Scheduling Using Automated Reasoning: A Case Study of the Car-Sequence Problem, Journal of Automated Reasoning, vol.2, pp.1-42, 1986.

G. Pesant, A Regular Language Membership Constraint for Finite Sequences of Variables, Proceedings of CP'04, pp.482-495, 2004.
DOI : 10.1007/978-3-540-30201-8_36

T. Petit, J. C. Régin, and C. Bessì-ere, Specific Filtering Algorithms for Over-Constrained Problems, Proceedings of CP'01, pp.451-463, 2001.
DOI : 10.1007/3-540-45578-7_31

T. Petit, J. C. Régin, and C. Bessiere, Specific Filtering Algorithms for Over-Constrained Problems, pp.451-463, 2001.
DOI : 10.1007/3-540-45578-7_31

J. C. Régin, Generalized Arc Consistency for Global Cardinality Constraints, Proceedings of AAAI'96, pp.209-215, 1996.

F. Rossi, P. Van-beek, and T. Walsh, Handbook of Constraint Programming, 2006.

M. Sánchez, S. De-givry, and T. Schiex, Mendelian Error Detection in Complex Pedigrees Using Weighted Constraint Satisfaction Techniques, Constraints, vol.57, issue.4, pp.130-154, 2008.
DOI : 10.1007/s10601-007-9029-5

T. Schiex, Arc Consistency for Soft Constraints, pp.411-424, 2000.
DOI : 10.1007/3-540-45349-0_30

T. Schiex, H. Fargier, and G. Verfaillie, Valued Constraint Satisfaction Problems: Hard and Easy Problems, Proceedings of IJCAI'95, pp.631-637, 1995.

D. Simoncini, D. Allouche, S. De-givry, C. Delmas, S. Barbe et al., Guaranteed Discrete Energy Optimization on Large Protein Design Problems, Journal of Chemical Theory and Computation, vol.11, issue.12, 2015.
DOI : 10.1021/acs.jctc.5b00594

M. A. Trick, A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints, Annals of Operations Research, vol.118, issue.1/4, pp.73-84, 2003.
DOI : 10.1023/A:1021801522545

M. Zytnicki, C. Gaspin, and T. Schiex, Bounds Arc Consistency for Weighted CSPs, Journal of Artificial Intelligence Research, vol.35, pp.593-621, 2009.

S. Foissac and T. Schiex, Integrating alternative splicing detection into gene prediction, BMC bioinformatics, vol.6, issue.1, 2005.
URL : https://hal.archives-ouvertes.fr/hal-01417735