Le clustering sous contraintes permet d'intégrer des connaissances expertes, que ce soit des contraintes classiques must-link ou cannot-link ou des contraintes plus complexes. La plupart des algorithmes de clustering probabilistes intègrent les contraintes en ajoutant un terme dans la fonction objectif représentant leur satisfaction. Ils intègrent donc difficilement différents types de contraintes et ne garantissent pas la satisfaction de toutes les contraintes. Nous proposons une méthode qui, à partir du résultat d'un algorithme de clustering sous la forme d'une matrice de probabilité d'affectation de points aux clusters, trouve la meilleure affectation qui satisfasse toutes les contraintes. Cette méthode peut s'appliquer à tout algorithme probabiliste y compris ceux utilisant l'apprentissage profond. Les expérimentations montrent que notre méthode est compétitive avec des méthodes parmi les plus récentes.