Maximum weight perfect matching problem with additional disjunctive conflict constraints

M. Hakan Akyüz, Kuban Altınel*, Temel Öncan

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

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 languageEnglish
Number of pages25
JournalNetworks
DOIs
Publication statusAccepted/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.

Fingerprint

Dive into the research topics of 'Maximum weight perfect matching problem with additional disjunctive conflict constraints'. Together they form a unique fingerprint.

Cite this