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
- Tam kamyon yüklü araç rotalama problemi varyantları için sütun üretimi temelli kesin çözüm yöntemlerinin geliştirilmesi ve uygulaması
Development and application of column generation-based exact solution methods for variants of the full truckload routing problem
TOYGAR EMRE
Doktora
Türkçe
2026
Endüstri ve Endüstri MühendisliğiÇukurova ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. RIZVAN EROL
- Kaynak kısıtlı proje programlama problemlerinin çözümü için yeni yöntem ve algoritmalar
New methods and algorithms for solving the resource-constrained project scheduling problem
İHSAN UĞUR
- Joint solution of the order batching, picker routing, storage location assignment, and scheduling problems
Sipariş gruplama, toplayıcı rotalama, depolama yeri atama ve çizelgeleme problemlerinin birlikte çözümü
OZAN RIDVAN AKSU
Doktora
İngilizce
2025
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA NECATİ ARAS
- Construction of the subtour
Gezgin satıcı probleminin alt tur engelleme kısıtlarının oluşturulması ve uzantıları
TOLGA BEKTAŞ