Constraint programming is a paradigm used for solving complex combinatorial problems with applications in logistics, healthcare, telecommunications, and many other fields. Among the many constraints used in constraint programming is the inverse constraint, necessary for matching items one to one, such as the placement of containers on ships and task scheduling. This paper presents a novel propagator for the inverse constraint, leveraging the Dulmage-Mendelsohn decomposition, implemented in the Pumpkin solver, to improve the performance of the solver. Unlike decompositions of the constraint into other simpler constraints, our approach utilizes the full bipartite graph structure of the constraint, generating stronger and more reusable explanations for unsolvable states.
Experiments were conducted on benchmark problems taken from the MiniZinc challenge, including the Time-Dependent Traveling Salesman Problem (TDTSP) and Perfect One-Factorization (P1F). These experiments demonstrated the effectiveness of the propagator. Achieving up to a 35% reduction in the time taken by the solver for some instances of TDTSP,the method also highlights limitations in the symmetric application of the inverse constraint on a single array. These findings advance our understanding of the propagation of the inverse constraint and show the potential of graph based techniques to optimize LCG solvers. Future work aims to optimize the implementation and explore its performance in relation to a broader spectrum of techniques.