Solving Various Weighted Matching Problems with Constraints

This paper studies the resolution of (augmented) weighted matching problems within a constraint programming framework. The first contribution of the paper is a set of branch-and-bound techniques that improves substantially the performance of algorithms based on constraint propagation and the second contribution is the introduction of weighted matching as a global constraint (MinWeightAllDifferent), that can be propagated using specialized incremental algorithms from Operations Research. We first compare programming techniques that use constraint propagation with specialized algorithms from Operations Research, such as the Busaker and Gowen flow algorithm or the Hungarian method. Although CLP is shown not to be competitive with specialized polynomial algorithms for "pure" matching problems, the situation is different as soon as the problems are modified with additional constraints. Using the previously mentioned set of techniques, a simpler branch-andbound algorithm based on constraint ..