Exact solution methods for the assignment problem with conflict constraints
Çatışma kısıtlı en büyük ağırlıklı atama problemi için kesin çözüm yöntemleri
- Tez No: 764377
- Danışmanlar: PROF. DR. İSMAİL KUBAN ALTINEL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Atama problemi, Dal kesme algoritması, Dallanma, Assignment problem, Branch-cutting algorithm, Branching
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Çatışmalı Atama Problemi (ÇAP), uyumsuzlukların varlığında maksimum ağırlık atamayı bulmakla ilgilenir. Uyumsuzluklar, çatışan kenar çiftleri nedeniyle ortaya çıkar ve çatışan çiftteki her iki kenar olası bir çözümde birlikte bulunamaz. Atama probleminden farklı olarak, ÇAP bir NP-zor problemdir ve ÇAP hakkında kesin çözüm prosedürlerini ortaya koyan sadece birkaç çalışma vardır; bu nedenle, ÇAP'yi çözmek için verimli bir kesin çözüm prosedürü bulmak bu çalışmanın motivasyonu olmuştur. Bildiğimiz kadarıyla, ÇAP'yi ele alan çalışmalarda Dal-Kesim çözüm yaklaşımı kullanılmamaktadır. Bu tezde, geliştirilen algoritmaların başarımlarını artırmak için tasarlanmış ek algoritmalarla birlikte çeşitli dallanma kuralları ve kesiler önerilmektedir. Önerilen algoritmaları ölçmek için öncelikle dallanma kurallarının başarımları değerlendirildi. Daha sonra seçilen dallanma kuralı ile ek algoritmaların etkinlikleri ölçüldü. Son olarak, seçilen dallanma kuralını ve bir tam sayı programlama ticari çözücüsünün varsayılan dallanma kuralını kullanarak, eklenen kesintilerin genel problemlere katkısı belirlendi. Bilgisayısal sonuçları, seçilen dallanma kuralına sahip Dal-Sınır algoritması ile düğümsel ve maksimal klik kesimli Dal-Kesme algoritmasının çok başarılı olduğunu göstermektedir.
Özet (Çeviri)
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 NP-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. Afterwards, 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.
Benzer Tezler
- Network flows with conflict constraints
Çatışma kısıtlı ağ akışları
ZEYNEP ŞUVAK
Doktora
İngilizce
2019
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. İSMAİL KUBAN ALTINEL
PROF. MUSTAFA NECATİ ARAS
- Atherosklerotik kalp hastalıklarında risk faktörleri
Risk factors in the coronary artery disease
MURAT SUHER
- Kam yapma aparatı
Cam milling attachment
ORHAN UZUN
Yüksek Lisans
Türkçe
1986
Makine MühendisliğiGazi ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. FEVZİ ERCAN
- Üniversite son sınıf kız öğrencilerinin sağlık-spor ve beslenme alışkanlıkları üzerine bir araştırma
Başlık çevirisi yok
SELMA ŞAHİN SALMAN
Yüksek Lisans
Türkçe
1986
SporGazi ÜniversitesiBeden Eğitimi ve Spor Ana Bilim Dalı
DOÇ. DR. EYYUP GÜNAY İSBİR