Graduate Program in Industrial Engineering.Altınel, İ. Kuban.Öncan, Temel.Çınar, Alim Buğra.2023-03-162023-03-162021.IE 2021 C56https://digitalarchive.library.bogazici.edu.tr/handle/123456789/13459In 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.30 cm.Matching theory.Parallel processing (Electronic computers)xv, 72 leaves ;