This thesis focuses on strong local consistencies for solving optimization problems in Cost Function Networks (aka weighted constraint networks). These methods provide the lower bound necessary for Branch-and-Bound search. We first study Virtual arc consistency (VAC), one of the strongest soft arc consistencies for Cost Function Networks, which is enforced by iteratively establishing hard arc consistency in a sequence of classical Constraint Networks. The algorithm enforcing VAC is improved by integrating dynamic arc consistency to exploit its incremental behavior. Dynamic arc consistency also allows to improve VAC when maintained VAC during search by efficiently exploiting the changes caused by branching operations.

Secondly, we are interested in stronger domain-based soft consistencies, inspired from similar consistencies in hard constraint networks (path inverse consistency, restricted or Max-restricted path consistencies). From each of these hard consistencies, many soft variants have been proposed for weighted constraint networks. The new consistencies provide lower bounds stronger than soft arc consistencies by processing triplets of variables connected two-by-two by binary cost functions. We have studied the properties of these new consistencies, implemented and tested them on a variety of problems. Although they do not always speed up problem resolution, they are the only one, among a large variety of methods, to solve some large difficult problems.