Optimization based heuristics for the graph partitioning problem

Çizge bölümleme problemi, bir çizgedeki düğümlerin önceden belirlenmiş eleman sayılı kümelere, uçları değişik kümelerde kalan kenarların toplam ağırlığı en küçük olacak şekilde bölünmesi ile ilgilenir. Çizge bölümleme probleminin paralel programlama, elektrik şebekeleri, sosyal ağlar, biyomedikal şebekeler ve çok geniş ölçekli tümleşik devre tasarımları gibi pek çok değişik alanda sayısız uygulamaları bulunmaktadır. Bu çalışmamızda özellikle büyük ölçekli problemler için kabul edilebilir süreler içinde iyi olurlu çözümler veren sezgisel yöntemlere odaklanıyoruz. Kullandığımız sezgisel yöntemler, çizge bölümleme probleminin farklı tamsayılı doğrusal programlama formülasyonlarının doğrusal programlama gevşetmelerinden elde edilen en iyi çözümleri girdi olarak almaktadır. Bu formülasyonlar, düğümlerin kümelere atanmasını modelleyen ikili karar değişkenlerine sahiptirler. Biz bu ikili atama değişkenlerinin gevşetmelerinden gelen en iyi değerlerin her birini, düğümlerin kümelere atanma uygunluklarını gösteren bir ölçü olarak ele alıyoruz. Bu yaklaşımı kullanarak iki farklı sezgisel yöntem öneriyoruz. İlk yöntemde, çizge bölümleme probleminin olurlu iyi çözümlerini, asıl problemin doğrusal programlama gevşetmelerindeki ikili atama değişkenlerinin en iyi değerlerini parametre olarak kullanan ikinci bir doğrusal programlama problemini çözerek hesaplamayı amaçlıyoruz. İkinci yöntemimiz rastlantısal bir algoritmadır. Bu yöntemde asıl problemin doğrusal programlama gevşetmesindeki her ikili atama değişkeninin en iyi değerini bir olasılık değeri olarak ele alıyoruz. Öncelikle, bu olasılık değerlerini kullanarak, kümelerin eleman sayıları kısıtlarını gözönüne almaksızın, düğümleri kümelere rastlantısal olarak atıyoruz. Sonra, açgözlü bir olurluluk onarımı prosedürü uygulayarak kümelerin eleman sayıları kısıtlarının sağlanmasını gerçekleştiriyoruz. Son çözümün kalitesi, asıl tamsayılı doğrusal programlama probleminin doğrusal programlama gevşetmesinin kalitesine bağlı olduğu için doğrusal programlama gevşetmesini sıkılaştıran birkaç geçerli eşitsizlikler sınıfını eklemeyi değerlendiriyoruz. Değişik özelliklere sahip rastgele yaratılmış çizge sınıflarında hesaplamalar gerçekleştiriyoruz. Değişik formülasyonların ve değişik geçerli eşitsizliklerin sezgisel yöntemlerimizin verdiği çözümlerin kaliteleri üzerindeki etkilerini özellikle inceliyoruz. Ayrıca, sezgisel yöntemlerimizin performanslarını, literatürde sıklıkla kullanılmış olan Kernighan-Lin sezgisel yöntemleriyle (KL yöntemi) karşılaştırıyoruz. Hesaplamalarımız, geliştirdiğimiz yöntemlerin genellikle KL yönteminden oldukça kısa işlemci zamanı kullandığını gösteriyor. Çok büyük örneklerde, hesaplamalardaki zorluğu yaratan kısım, doğrusal programlama gevşetmelerini çözmek oluyor. Bizim geliştirdiğimiz sezgisel yöntemler, KL yöntemini çözüm kalitesi olarak aşamasa da, sezgisel yöntemlerimizden gelen çözümleri KL yönteminde başlangıç noktası olarak kullanmak, bazı örnekler için daha iyi sonuçlar elde etmemizi sağlıyor.