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ı: 61
Ö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
- A new approach to satellite communication: Harnessing the power of reconfigurable intelligent surfaces
Uydu iletisimine yeni bir yaklaşım: Yeniden yapılandırılabı̇lı̇r akıllı yüzeylerden faydalanma
KÜRŞAT TEKBIYIK
Doktora
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. GÜNEŞ ZEYNEP KARABULUT KURT
- Operasyonel teknolojiler için güvenli mimari tasarımı
Design secure architecture for operational technology
MEHMET YAVUZ YAĞCI
Doktora
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Üniversitesi-CerrahpaşaBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUHAMMED ALİ AYDIN
- Fraud detection in blockchain cryptocurrencies
Blokzincir kripto paralarda dolandırıcılık tespiti
OSMAN KUMAŞ
Yüksek Lisans
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBahçeşehir ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ALPER CAMCI
DOÇ. AKHAN AKBULUT
- An iterative approach to keyword search in sign language
İşaret dilinde anahtar sözcük aramaya yinelemeli bir yaklaşım
MANSUR YEŞİLBURSA
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. MURAT SARAÇLAR
- Performance analysis of machine learning for predicting ionic liquid toxicity
İyonik sivi toksisitesinin tahmini için makine öğreniminin performans analizi
SAFA SADAGHIYANFAM
Doktora
İngilizce
2025
Biyomühendislikİzmir Katip Çelebi ÜniversitesiBiyomedikal Teknolojiler Ana Bilim Dalı
DOÇ. DR. YALÇIN İŞLER