Maksimum seçmeli ağaç problemi için tamsayılı programlama formülasyonları ve kesme düzlemi algoritmaları

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.