Maximum Weight Perfect Matching Problem With Additional Disjunctive Conflict Constraints

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.

About Hakan

M. Hakan Akyüz received his PhD in industrial engineering from Boğaziçi University. He worked as a postdoctoral fellow at Hong Kong University of Science and Technology until 2013. He joined the Department of Industrial Engineering at Galatasaray University in 2014 as an assistant professor and became an associate professor in 2018. He has been part of the econometrics department at Erasmus University Rotterdam since 2020. His research interests span logistics, algorithms, and machine learning.