Integer programming formulations and cutting plane algorithms for the maximum selective tree 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: 2022

Tezin Dili: İngilizce

Öğrenci: ÖMER BURAK ONAR

Danışman: TINAZ EKİM

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

Özet:

Bu tezde Maksimum Tetiklenmiş Ağaç Problemi'nin bir çeşit genelleştirilmesi olarak Maksimum Seçmeli Ağaç Problemi (MSelTP) ele alınıyor. MSelTP, düğümleri kümeleştirilmiş yönsüz bir çizge üzerinde, her bir küme başına en fazla bir tane düğüm seçecek ve bu seçimin tetiklediği çizge bir ağaç olacak şekilde en çok sayıda düğüm seçebilmeyi hedefler. Bildiğimiz kadarıyla, birçok benzer optimizasyon problemi çalışılmış olmasına rağmen, MSelTP'nin daha önce çalışılmadığını söyleyebiliriz. MSelTP için biri bağlantılılık kısıtlarına dayalı, diğeri ise döngü eleme kısıtlarına dayalı olmak üzere iki tane karışık tamsayılı programlama formülasyonu önerdik. İlaveten, problemi optimum olarak çözebilmek için iki tane kesme düzlemi yöntemi geliştirdik. Bu iki çözüm yöntemini ve polinom sayıda kısıt içeren tamsayılı programlama formülasyonunu kıyaslamak amacıyla küme sayısı 25'e kadar olan, düğüm sayısı 250'ye kadar olan ve değişen yoğunluklara sahip çizgelerde hesaplamalı deneyler gerçekleştirdik. Deneylerimiz, CPAXnY algoritmasının diğer yöntemlere göre genel olarak daha iyi çalıştığına işaret etmekte, ancak düşük yoğunluklu ve kümelerindeki ortalama düğüm sayısı çok olan çizgelerde CPAX algoritmasının performansı ortalama süre bakımından daha iyi sonuç vermektedir.