Research Information System
17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019, Enschede, Netherlands, 1 - 03 July 2019, pp.111-114, (Full Text)
In this work, we consider the maximum weight perfect matching problem with conflicts, which is known to be NP-hard. We propose a tailor-made branch-and-bound algorithm with a non-dichotomized branching rule based on a maximum weight stable set relaxation of the problem. We have realized preliminary computational experiments on randomly generated test instances and compared the computational performance of the new algorithm with the one of a well-known commercial solver. Based on the obtained results we can say that it is promising.