Branch - and - price algorithms for the maximum weight perfect matching problem with conflict constraints
| dc.contributor | Graduate Program in Industrial Engineering. | |
| dc.contributor.advisor | Altınel, İ. Kuban. | |
| dc.contributor.advisor | Öncan, Temel. | |
| dc.contributor.author | Çınar, Alim Buğra. | |
| dc.date.accessioned | 2023-03-16T10:30:19Z | |
| dc.date.available | 2023-03-16T10:30:19Z | |
| dc.date.issued | 2021. | |
| dc.description.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. | |
| dc.format.extent | 30 cm. | |
| dc.format.pages | xv, 72 leaves ; | |
| dc.identifier.other | IE 2021 C56 | |
| dc.identifier.uri | https://digitalarchive.library.bogazici.edu.tr/handle/123456789/13459 | |
| dc.publisher | Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2021. | |
| dc.subject.lcsh | Matching theory. | |
| dc.subject.lcsh | Parallel processing (Electronic computers) | |
| dc.title | Branch - and - price algorithms for the maximum weight perfect matching problem with conflict constraints |