Integer programming formulations and benders decomposition for maximum induced matching problem

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye

Tezin Onay Tarihi: 2016

Tezin Dili: İngilizce

Öğrenci: BETÜL AHAT

Danışman: TINAZ EKİM

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Bu tezde Maksimum Tetiklenmiş Eşleştirme problemini (MIM), en büyük boyuta sahip tetiklenmiş eşleştirme bulma, inceledik. Bu problem genel çizgeler için NP-zor'dur. Literatürde bulunan formülasyonlardan daha az karar değişkenine sahip tamsayı programlama formülasyonu geliştirdik. Daha sonra, bu problemi düğüm-ağırlıklı çizgeler için genişleterek Maksimum Düğüm-Ağırlıklı Tetiklenmiş Eşleştirme problemini (MVWIM) tanıttık. MIM'in kenar-ağırlıklı versiyonunu tanıttık ve buna Maksimum Kenar-Ağırlıklı Tetiklenmiş Eşleştirme problemi (MEWIM) adını verdik. Literatürde bulunan formülasyonları ve bizim formülasyonumuzu MVWIM ve MEWIM örneklerini çözmek için uyarladık. Maksimum Ağırlıklı Tetiklenmiş Eşleştirme probleminin (MWIM) genelleştirilmiş versiyonunda hem düğümler hem de kenarların ağırlıklı olduğunu varsaydık ve bunun için bir tamsayı programlama formülasyonu verdik. Bu formülasyonda çok fazla karar değişkeni ve kısıt olduğundan, problemi daha küçük problemlere bölmek için Benders parçalama yaklaşımı uyguladık. Daha sonra, algoritmamızın verimliliğini geliştirmek için formülasyonumuza bazı geçerli eşitsizlikler ekledik. Metodumuzun performansını test edebilmek için, farklı yoğunluklara sahip rassal çizgeler ürettik. Sayısal sonuçlara bakarak, yaklaşımımızın literatürde bulunan diğer formülasyonlara göre orta ve büyük yoğunluğa sahip örnekleri belirgin derecede daha hızlı çözdüğü görülebilir.