Optimization based heuristics for the graph partitioning problem
Çizge bölümleme problemi için eniyileme tabanlı sezgisel yöntemler
- Tez No: 397220
- Danışmanlar: DOÇ. DR. EMRE ALPER YILDIRIM
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 75
Özet
Ç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.
Özet (Çeviri)
The graph partitioning problem is concerned with partitioning the vertices of a graph into a prespecified number of clusters with given cardinalities so as to minimize the total weight of the edges that have two endpoints in different clusters. This problem has numerous applications in various fields, including parallel processing, power grids, social networks, biomedical networks, and VLSI design. Our focus in this study is on heuristic methods that yield good feasible solutions in a reasonable amount of time, especially for large-scale instances. Our heuristic methods are based on optimal solutions of linear programming relaxations of different integer linear programming formulations of the graph partitioning problem. In particular, these formulations employ binary variables for determining the assignment of each vertex to each cluster. We treat the optimal value of the relaxed version of each of these binary assignment variables as a measure of the likelihood of the assignment of each vertex to each cluster. Using this approach, we propose two different heuristic methods. In the first method, we aim to compute a good feasible solution of the graph partitioning problem by solving another linear programming problem whose parameters are given by the optimal values of the binary assignment variables in the linear programming relaxation of the original problem. The second method is a randomized algorithm, in which we treat the optimal value of each binary assignment variable in the original linear programming relaxation as a probability measure. We randomly assign each vertex to each cluster using the corresponding probabilities without taking into consideration the cardinality constraint on each cluster. We then apply a greedy feasibility restoration procedure in an attempt to satisfy the cardinality constraints of clusters. Since the quality of the final solutions heavily depends on the quality of the linear programming relaxation of the original integer linear programming problem, we consider adding several classes of valid inequalities in an attempt to strengthen the linear programming relaxation. We perform computational experiments on several classes of randomly generated graphs with different characteristics. In particular, we study the effects of different formulations and different valid inequalities on the quality of the resulting feasible solutions computed by our heuristic methods. We also compare the performance of our heuristic methods with the well-known Kernighan-Lin heuristic method (KL method). Our computational results reveal that our methods usually take considerably less CPU time than the KL method. For very large instances, solving the linear programming relaxation becomes a computational bottleneck. While our heuristic methods, in general, do not seem to outperform the KL method in terms of the solution quality, using the solutions generated by our heuristic methods as initial solutions for the KL method has the potential to lead to further improvements on several instances.
Benzer Tezler
- Kernel and launch time optimizations for deep learning frameworks
Derin öğrenme çerçeveleri için çekirdek ve ateşleme zamanı iyileştirmeleri
DOĞA DİKBAYIR
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ DİDEM UNAT
- Büyük ölçekli havayolu ekip eşleme problemlerinin çözümü için bir kolon türetme stratejisi
A column generation strategy for large scale airline crew pairing problems
BAHADIR ZEREN
Doktora
Türkçe
2017
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. İBRAHİM OZKOL
- Polyhedral approaches to hypergraph partitioning and cell formation
Hiperçizge parçalama problemine polyhedral yaklaşımlar ve hücre belirlenmesi
LEVENT KANDİLLER
Doktora
İngilizce
1994
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiDOÇ.DR. MUSTAFA AKGÜL
- Hyper-heuristics for grouping problems
Gruplama problemleri için çok hedefli üst buluşsallar
MURAT BİRBEN
Yüksek Lisans
İngilizce
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ENDER ÖZCAN
- Graph neural networks-based primal heuristics for combinatorial optimization
Kombinatoryal optimizasyon için grafik sinir ağları tabanlı birincil sezgisel yöntem
FURKAN CANTÜRK
Yüksek Lisans
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÖzyeğin ÜniversitesiYapay Zeka Ana Bilim Dalı
DR. ÖĞR. ÜYESİ REYHAN AYDOĞAN
PROF. DR. OKAN ÖRSAN ÖZENER