Branch - and - price algorithms for the maximum weight perfect matching problem with conflict constraints

Abstract

In this thesis, we consider the Maximum Weight Perfect Matching Problem with Conflict Constraints (MWPMC), which is a generalization of the well-known the Maxi mum Weight Perfect Matching Problem (MWPMP). Although MWPMC is a relatively recent problem, there are applications modeled as MWPMC or using MWPMC as a subproblem in a wide spectrum from molecular biology to computer graphics. MW PMC is proven to be N P-hard. Hence, a high-performance solution approach is crucial for both existing and potential applications. There are a number of combinatorial optimization problems in the literature involving conflict constraints. We observe that some of the related studies had sat isfactory results with Branch-and-Price (B&P) algorithm. Also, no studies aiming to solve MWPMC by using B&P exist to the best of our knowledge. Therefore, we study the question of how B&P algorithm can be applied to the MWPMC. We propose sev eral Integer Programming (IP) formulations for the MWPMC and build corresponding B&P schemes. Then, B&P algorithms are implemented and tested. According to our findings, some of the proposed schemes show performance that can compete with the commercial solvers.