Abstract
In this work, we consider the maximum weight perfect matching problem with conflicts,
which is known to be N P-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.
which is known to be N P-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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization |
| Place of Publication | Enschede |
| Pages | 111-114 |
| Volume | DSI Workshop Proceedings Series (online) WP19-01 |
| Publication status | Published - Jul 2019 |
| Externally published | Yes |
Bibliographical note
CTW 2019Proceedings of the 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization
J.L. Hurink, S. Klootwijk, B. Manthey, V.M.J.J. Reijnders, M.H.H. Schoot Uiterkamp (eds.)
Enschede, University of Twente, Faculty of Electrical Engineering, Mathematics and Computer
Science 1–3 July 2019
Erasmus Sectorplan
- Sectorplan SSH-Breed