Çatışma kısıtlı en büyük ağırlıklı atama problemi için kesin çözüm yöntemleri

Ç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.