Abstract
We focus on an extension of the maximum weight perfect matching problem with additional disjunctive conflict constraints in conjunction with the degree and binary restrictions. Given a simple graph with a nonnegative weight associated with each edge and a set of conflicting edges, the perfect matching problem with conflict constraints consists of finding a maximum weight perfect matching without any conflicting edge pair. Unlike the well-known ordinary maximum weight perfect matching problem this one is strongly NP-hard. We propose two branch-and-bound algorithms for the exact solution of the problem. The first one is based on an equivalent maximum weight stable set formulation with an additional cardinality restriction obtained on the graph representing conflict relations and uses the information coming from its maximal stable sets. The second one is essentially a recursive depth first search scheme that benefits from simple upper bounds incorporated with a fast infeasibility detection procedure to prune the branch-and-bound tree. According to the extensive computational tests it is possible to say that they are both very efficient.
| Original language | English |
|---|---|
| Number of pages | 25 |
| Journal | Networks |
| DOIs | |
| Publication status | Accepted/In press - 2022 |
Bibliographical note
Funding Information:We gratefully acknowledge the support of TÜBİTAK (The Scientific and Technological Research Council of Turkey) with grant no. 217M477. Also we would like to express our sincere gratitudes for Dr. Sewell who has kindly shared his codes.
Funding Information:
TUBITAK (The Scientific and Technological Research Council of Turkey) with grant no. 217M477 Funding information
Publisher Copyright:
© 2022 Wiley Periodicals LLC.