We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Maximum weight perfect matching problem with additional disjunctive conflict constraints.
- Authors
Akyüz, M. Hakan; Altınel, İ. Kuban; Öncan, Temel
- 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 풩풫‐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.
- Subjects
TREE pruning; INTEGER programming; ALGORITHMS; MATCHING theory; WEIGHTED graphs
- Publication
Networks, 2023, Vol 81, Issue 4, p465
- ISSN
0028-3045
- Publication type
Article
- DOI
10.1002/net.22139