Graph attention network (GAT) based branching in combinatorial optimization problems
Kombinatoryal optimizasyon problemlerinde graf dikkat ağı (GAT) bazlı dallanma
- Tez No: 925716
- Danışmanlar: PROF. DR. METİN TÜRKAY
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bu çalışmada, Kombinatoryal Optimizasyon problemlerinin çözümünde kullanılan Dallandırma & Sınırlandırma algoritmasının en kritik bileşenlerinden biri olan dallanma aşamasında, Güçlü Dallanma (Strong Branching) stratejisinin, Graf Dikkat Ağı (GAT) tabanlı bir yöntem ile, taklit edilmesi hedeflenmiştir. Güçlü Dallanma, arama ağacını kısa tutması nedeniyle düğüm sayısı açısından etkili bir strateji olmasına rağmen, her bir dallanma adayı değişken için her düğümde lineer programlama problemini iki kez çözmesi gerektiğinden oldukça zaman alıcıdır. Güçlü Dallanma stratejisinin zaman maliyetini ortadan kaldırmak için, GAT tekniğinin kullanımı ile Güçlü Dallanma benzeri kararlar verebilecek bir fonksiyon öğrenilmesi amaçlanmıştır. Literatürde, Graf Konvolüsyonel Sinir Ağı (GCNN) kullanarak Güçlü Dallanma stratejisini başarıyla taklit eden çalışmalar bulunmaktadır. GCNN yönteminde, bir düğüm için tüm komşu düğümler aynı öneme sahiptir. Buna karşılık, GAT mimarisi, komşu düğümlerin bir düğüm için farklı önem seviyelerine sahip olmasına olanak tanır. Bu nedenle, GAT tabanlı yöntemlerin daha iyi sonuçlar vereceği hipotez edilmektedir. Bu çalışmada yapılan deneyler, GAT mimarisinin, GCNN mimarisine kıyasla Güçlü Dallanma stratejisine daha yakın kararlar sağladığını göstermiştir. GAT tabanlı yöntemler, problemleri GCNN'ye kıyasla daha az düğümle çözmeyi mümkün kılmaktadır. Özetle, GAT, etkili ancak yavaş olan Güçlü Dallanma stratejisini taklit etmek için umut verici bir araçtır.
Özet (Çeviri)
In this study, the main aim is to imitate the Strong Branching strategy during the branching phase, which is one of the most critical components of the Branch & Bound algorithm used for solving Combinatorial Optimization problems, by implementing a Graph Attention Network (GAT)-based method. Strong Branching is an effective strategy in terms of the number of nodes, keeping the search tree short. However, it is highly timeconsuming because it solves the linear programming problem twice for each branching candidate variable at each node. To eliminate the time cost of the Strong Branching strategy, this study attempts to learn a function implementing the GAT technique that can make Strong Branching-like decisions in a shorter time. In the literature, there are studies that successfully imitate the Strong Branching strategy using Graph Convolutional Neural Network (GCNN). In the GCNN method, all neighbouring nodes have the same importance for a node. In contrast, the GAT architecture allows neighbouring nodes to have different levels of importance for a node. Therefore, it is hypothesized that GAT-based methods will yield better results. Experiments conducted in this study have shown that the GAT architecture provides decisions closer to the Strong Branching strategy compared to the GCNN architecture. GAT-based methods enable problems to be solved with fewer nodes compared to GCNN. In summary, GAT is a promising tool for imitating the effective yet slow Strong Branching strategy.
Benzer Tezler
- Üzüm sularının pastörizasyonu ve kontsantresi sırasında hidroksimetilfurfural oluşumu üzerinde bir araştırma
Başlık çevirisi yok
ŞERİFE ŞAHİN
Yüksek Lisans
Türkçe
1985
Gıda MühendisliğiEge ÜniversitesiTarım Ürünleri Teknolojisi Ana Bilim Dalı
DOÇ. DR. AYDIN URAL
- Çekirdeksiz kuru üzümde uygulanan politikanın Ege Bölgesinde üretim ve üretici açısından sonuçlarının değerlendirilmesi
Başlık çevirisi yok
GÜVEN ÖZERİN
- Çekirdeksiz kuru üzümlerde aflatoksin B1, B2, G1, G2 tayini için mevcut bazı metotların karşılaştırılması üzerinde bir çalışma
Başlık çevirisi yok
DİLEK BOYACIOĞLU
Yüksek Lisans
Türkçe
1985
Gıda MühendisliğiEge ÜniversitesiGıda Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MERAL GÖNÜL
- Zymomonas mobilis NRRL B-14023 bakterisi ile şeker pancarı melası ve kuru üzümden etanol üretimi
Başlık çevirisi yok
ÜLKÜ BAŞER