]. E. Références, P. Boros, and . Hammer, Pseudo-Boolean Optimization, Discrete Appl. Math, vol.123, issue.1, pp.155-225, 2002.

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

D. Cohen, M. Cooper, P. Jeavons, and A. Krokhin, A Maximal Tractable Class of Soft Constraints, Journal of Artificial Intelligence Research, vol.22, pp.1-22, 2004.

D. Cohen, M. Cooper, P. Jeavons, and A. Krokhin, The complexity of soft constraint satisfaction, Artificial Intelligence, vol.170, issue.11, pp.983-1016, 2006.
DOI : 10.1016/j.artint.2006.04.002

M. Cooper, S. De-givry, and T. Schiex, Optimal soft arc consistency, Proc. of IJCAI-07, pp.68-73, 2007.

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. Cooper, S. De-givry, M. Zytnicki, F. Heras, and J. Larrosa, Minimization of locally-defined submodular functions by Optimal Soft Arc Consistency Existential arc consistency : Getting closer to full arc consistency in weighted csps, Proc. of IJCAI-05, pp.84-89, 2005.

F. Heras, J. Larrosa, and A. Oliveras, MiniMax- Sat : A New Weighted Max-SAT Solver, Proc. of SAT'2007, number 4501 in LNCS, pp.41-55, 2007.

P. Jeavons and M. Cooper, Tractable constraints on ordered domains, Artificial Intelligence, vol.79, issue.2, pp.327-339, 1995.
DOI : 10.1016/0004-3702(95)00107-7

L. Khatib, P. Morris, R. Morris, and F. Rossi, Temporal constraint reasoning with preferences

J. Kratica, D. Tosic, V. Filipovic, and I. Ljubic, Solving the simple plant location problem by genetic algorithm, RAIRO - Operations Research, vol.35, issue.1, pp.127-142, 2001.
DOI : 10.1051/ro:2001107

C. Li, F. Manyà, and J. Planes, Exploiting Unit Propagation to Compute Lower Bounds in Branch and Bound Max-SAT Solvers, Proc of CP-05, number 3709 in LNCS, pp.403-414, 2005.
DOI : 10.1007/11564751_31

J. Régin, T. Petit, C. Bessì, and J. Puget, New Lower Bounds of Constraint Violations for Over-Constrained Problems, Proc. of CP-01, number 2239 in LNCS, pp.332-345, 2001.
DOI : 10.1007/3-540-45578-7_23

T. Schiex, Arc Consistency for Soft Constraints, Proc. of CP-00, 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, Proc. of IJCAI-95, pp.631-637, 1995.

D. Schlesinger, Exact Solution of Permuted Submodular MinSum Problems In Energy Minimization Methods in Computer Vision and Pattern Recognition, LNCS, issue.4679, pp.28-38, 2007.

M. Schlesinger, Sintaksicheskiy analiz dvumernykh zritelnikh signalovv usloviyakh pomekh (Syntactic analysis of two-dimensional visual signals in noisy conditions), Kibernetika, vol.4, pp.113-130, 1976.

T. Werner, A Linear Programming Approach to Max-Sum Problem: A Review, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.29, issue.7, pp.1165-1179, 2007.
DOI : 10.1109/TPAMI.2007.1036

M. Zytnicki, C. Gaspin, and T. Schiex, A new local consistency for weighted CSP dedicated to long domains, Proceedings of the 2006 ACM symposium on Applied computing , SAC '06, pp.394-398, 2006.
DOI : 10.1145/1141277.1141367