Iterated Exact and Heuristic Algorithms for the Minimum Cost Bipartite Perfect Matching Problem with Conflict Constraints

ÖNCAN T., ALTINEL İ. K.

IEEE International Conference on Industrial Engineering and Engineering Management (IEEE IEEM), Singapore, Singapur, 10 - 13 Aralık 2017, ss.1032-1036 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Basıldığı Şehir: Singapore
  • Basıldığı Ülke: Singapur
  • Sayfa Sayıları: ss.1032-1036
  • Galatasaray Üniversitesi Adresli: Evet

Özet

In this study we address the Minimum Cost Bipartite Perfect Matching Problem with Conflict Pair Constraints (MCBPMPC) on bipartite graphs. Given a cost attached to each edge, the MCBPMPC is to find a minimum cost perfect matching on a bipartite graph such that at most one edge is chosen from a set of conflicting edge pairs. Two formulations, specially tailored iterated exact and heuristic algorithms are introduced. Computational experiments are performed on randomly generated instances. According to the extensive experiments, the iterated exact algorithm yields promising performance.