Nous proposons une nouvelle décomposition additive des tables de probabilités qui préserve l'équivalence de la distribution jointe permettant de réduire la taille des potentiels, sans ajout de nouvelles variables. Nousformulons le problème de Most Probable Explanation(MPE) dans les réseaux probabilistes comme un problème de satisfaction de contraintes pondérées (Weighted Constraint Satisfaction Problem WCSP). Notre décomposition par paire permet de remplacer une fonction de coûts par des fonctions d'arités plus petites. Le WCSP résultant de cette décomposition est plus facile à résoudre par les techniques de l'état de l'art des WCSP. Même si tester la décomposition par paire est équivalent à tester l'indépendance de paire du réseau de croyances original, nous montrons comment le tester efficacement et l'appliquer, même avec des contraintes dures. De plus, nous inférons une information supplémentaire à partir des fonctions de coûts non binaires réultantes par projection&soustraction dans leurs fonctions binaires. Nous observons d'importantes améliorations grâce au pré-traitement avec la décompostion de paire et la projection&soustraction comparée aux sol-veurs actuels de l'état de l'art sur deux ensembles deproblèmes difficiles.