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: Belirtilmemiş.
- 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ı: 103
Ö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
- Gezgin satıcı problemi
Traveling salesman problem
VOLKAN M. ÖZALP
Yüksek Lisans
Türkçe
1995
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. FÜSUN ÜLENGİN
- Belirsizlik altında heterojen filo ve zaman pencereli rotalama problemi: Hızlı tüketim sektöründe bir uygulama
Heterogeneous vehicle routing with time windows under uncertainty: Implementation in fast moving goods industry
ELÇİN ÖZEN KURU
Yüksek Lisans
Türkçe
2018
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. FERHAN ÇEBİ
- Construction of the subtour
Gezgin satıcı probleminin alt tur engelleme kısıtlarının oluşturulması ve uzantıları
TOLGA BEKTAŞ
- A hbyrid genetic algorithm for mixed-model assembly line balancing problem with parallel workstation assignment
Paralel istasyon atamalı karışık tipli montaj hattı dengeleme probleminin melez genetik algoritma ile çözümü
ŞENER AKPINAR
Yüksek Lisans
İngilizce
2009
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Bölümü
PROF. DR. G. MİRAÇ BAYHAN