zbMATH — the first resource for mathematics

Solving various weighted matching problems with constraints. (English) Zbl 0949.90058
Summary: This paper studies the resolution of (augmented) weighted matching problems within a constraint programming (CP) framework. The first contribution of the paper is a set of techniques that improves substantially the performance of branch-and-bound algorithms based on constraint propagation and the second contribution is the introduction of weighted matching as a global constraint (weighted matching), 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 CP 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-and-bound algorithm based on constraint propagation can outperform a complex specialized algorithm. These techniques have been applied with success to the traveling salesman problems [Y. Caseau and F. Laburthe, Solving small TSPs with constraints. Proc. of the 14th International Conference on Logic Programming (L. Naish ed.), The MIT Press (1977)] which can be seen as an augmented matching problem. We also show that an incremental version of the Hungarian method can be used to propagate a weighted matching constraint. This is an extension to the weighted case of the work of J. C. Regin [A filtering algorithms for constraints of difference in CSPs, Proc. of AAAI (1994)] which we show to bring significant improvements on a timetabling example.

90B99 Operations research and management science
90C90 Applications of mathematical programming
Full Text: DOI