Arşiv ve Dokümantasyon Merkezi
Dijital Arşivi

Exact solution methods for the assignment problem with conflict constraints

Basit öğe kaydını göster

dc.contributor Graduate Program in Industrial Engineering.
dc.contributor.advisor Altınel, İ. Kuban.
dc.contributor.author Arslan, Elif.
dc.date.accessioned 2023-10-15T07:40:18Z
dc.date.available 2023-10-15T07:40:18Z
dc.date.issued 2022
dc.identifier.other IE 2022 A77
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/19790
dc.description.abstract The Assignment Problem with Conflict Constraints (APC) deals with finding a maximum weight assignment in the presence of incompatibilities. The incompatibilities are constituted by the conflicting edge pairs such that both edges in a conflicting pair cannot be in a feasible solution. Unlike the assignment problem, APC is a N P hard problem; therefore, it brings about the importance of finding efficient solution procedures for APC. Yet, there are only a few studies on APC that put forward exact solution procedures. To the best of our knowledge, this is the first study which proposes Branch & Cut algorithms for the solution of APC. Within the computational analysis, we first evaluated the performance of Branch & Bound with different branching rules. After wards, we assessed the performance of additional algorithms with the best performing branching rule. Finally, we checked the contribution of the added cuts to the overall problem with the selected branching rule and the default branching rule of the mixed integer linear programming commercial solver. The computational results showed that the Branch & Bound algorithm with the best performing branching rule, the Branch & Cut algorithm with clique cuts and the Branch & Cut algorithm with combination of clique and cycle cuts performed better compared to the state-of-art commercial solver.
dc.publisher Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2022.
dc.subject.lcsh Assignment problems (Programming)
dc.title Exact solution methods for the assignment problem with conflict constraints
dc.format.pages xiii, 91 leaves


Bu öğenin dosyaları

Bu öğe aşağıdaki koleksiyon(lar)da görünmektedir.

Basit öğe kaydını göster

Dijital Arşivde Ara


Göz at

Hesabım