Maximum weight perfect matching problem with additional disjunctive conflict constraints

Akyüz M. H., Altınel İ. K., ÖNCAN T.

Networks, cilt.81, sa.4, ss.465-489, 2023 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 81 Sayı: 4
  • Basım Tarihi: 2023
  • Doi Numarası: 10.1002/net.22139
  • Dergi Adı: Networks
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, PASCAL, Aerospace Database, Applied Science & Technology Source, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, zbMATH, Civil Engineering Abstracts
  • Sayfa Sayıları: ss.465-489
  • Anahtar Kelimeler: branch-and-bound, conflict constraints, integer programming, maximum weight perfect matching, stable sets
  • Galatasaray Üniversitesi Adresli: Evet

Özet

© 2022 Wiley Periodicals LLC.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 (Formula presented.) -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.