Maksimum tetiklenmiş eşleştirme problemi için tamsayı programlama formülasyonu ve benders ayrıştırması

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.