Iterated exact and heuristic algorithms for the minimum cost bipartite perfect matching problem with conflict constraints

摘要

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.