A Branch-and-Bound Algorithm for the Minimum Cost Bipartite Perfect Matching Problem with Conflict Pair Constraints

In this study we consider the Minimum Cost Bipartite Perfect Matching Problem with Conflict Pair Constraints (MCBPMPC) on bipartite graphs. Given a bipartite graph G with a cost associated with each edge and a conflict set of edge pairs, the MCBPMPC consists of finding a perfect matching with the lowest total cost such that no more than one edge is selected from each pair in the conflict set. A specially tailored branch-and-bound (B&B) algorithm is introduced. Computational experiments are performed on randomly generated instances. According to the extensive experiments, the suggested B&B algorithm yields promising results compared to a state-of-the-art mixed integer linear programming solver.