Graph neural networks-based primal heuristics for combinatorial optimization
Kombinatoryal optimizasyon için grafik sinir ağları tabanlı birincil sezgisel yöntem
- Tez No: 821876
- Danışmanlar: DR. ÖĞR. ÜYESİ REYHAN AYDOĞAN, PROF. DR. OKAN ÖRSAN ÖZENER
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Endüstri ve Endüstri Mühendisliği, Matematik, Computer Engineering and Computer Science and Control, Industrial and Industrial Engineering, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: İngilizce
- Üniversite: Özyeğin Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Yapay Zeka Ana Bilim Dalı
- Bilim Dalı: Yapay Zeka Bilim Dalı
- Sayfa Sayısı: 105
Özet
Farklı örnekler için elde edilen çözümlerin yapısı incelenerek, kombinatoryal optimizasyon (KO) problemlerinin yapısı ve davranışı anlaşılabilir ve bunları çözmek için verimli algoritmalar geliştirilebilmektedir. Özellikle Grafik Sinir Ağları (GSA'lar) gibi Makine Öğrenmesi teknikleri, bu zahmetli tasarım sürecini parametrize etme ve otomatikleştirme için umut vadetmektedir. GSA'ların tümevarımsal yanlılığı, KO problemlerinin karışık tamsayılı programlama (KTP) formülasyonlarındaki karar değişkenleri ve kısıtların ilişkisel temsili üzerinden çözümleri öğrenmeyi mümkün kılmaktadır. Eğitilmiş GSA'lar, CO problemleri için yüksek kaliteli ve uyarlı çözümler oluşturmak için temel sezgisel yöntemlerle birlikte kullanılabilmektedir. Ancak, mevcut GSA tabanlı uçtan uca öğrenme yaklaşımları, ölçeklenebilir model eğitimi ve genelleştirme açısından çeşitli sınırlılıklar nedeniyle genellikle küçük ölçekli problem örnekleri üzerinden değerlendirilmiştir. Bu sorunu ele alan çalışmamız, büyük ölçekli KO problemlerinin küçültülmüş örneklerinin optimal çözümlerinin uçtan uca öğrenmesine dayanmaktadır. KO için kullanılan yeni bir GSA modeli için çeşitli geliştirmeler yaparak eğitimde kullanılanlardan daha büyük ölçekteki örneklerde modelin genelleme yapabilmesi sağlanmaktadır. Ayrıca, karar değeri tahminlerine dayalı olarak çözüm aramanın nasıl yapılandırılacağını otomatikleştirmek için model belirsizliğine dayalı iki aşamalı bir temel sezgisel yöntem önermekteyiz. Modellerimiz, yaygın olarak kıyaslanan beş KO probleminin 16 kat büyütülmüş örneklerinde genelleme yapabilmektedir. Problem büyüklüğü arttıkça mevcut GSA tabanlı KO yaklaşımlarının gitgide düşen performansının aksine, modellerimizi kullanan KO işlem hatları, son teknoloji bir KTP çözücüsü olan CPLEX'e göre gitgide artan bir performans iyileştirmesi sunmaktadır. Önerilen belirsizlik temelli temel sezgisel yöntemler, yüksek kaliteli çözümleri elde etmek için büyük bir hız artışı sağlamakta ve 16 kat büyütülmüş örneklerde %6 ila %75 daha iyi optimalite aralığı ve %45 ila %99 daha iyi temel aralık değerleri sağlamaktadır. Tüm bu kazanımlar, çözüm kalitesinden ödün vermeden hesaplama açısından verimli bir modelleme yaklaşımıyla elde edilmektedir.
Özet (Çeviri)
By examining the patterns of solutions obtained for varying instances, one can gain insights into the structure and behavior of combinatorial optimization (CO) problems and develop efficient algorithms for solving them. Machine learning techniques, especially Graph Neural Networks (GNNs), have shown promise in parametrizing and automating this laborious design process. The inductive bias of GNNs allows for learning solutions to mixed-integer programming (MIP) formulations of constrained CO problems with a relational representation of decision variables and constraints. The trained GNNs can be leveraged with primal heuristics to construct high-quality feasible solutions to CO problems quickly. However, current GNN-based end-to-end learning approaches have limitations for scalable training and generalization on larger-scale instances; therefore, they have been mostly evaluated over small-scale instances. Addressing this issue, our study builds on end-to-end learning of optimal solutions to the downscaled instances of given large-scale CO problems. We introduce several improvements on a recent GNN model for CO to generalize on instances of a larger scale than those used in the training. We also propose a two-stage primal heuristic strategy based on uncertainty-quantification to automatically configure how solution search relies on the predicted decision values. Our models can generalize on 16x upscaled instances of commonly benchmarked five CO problems. Unlike the regressive performance of existing GNN-based CO approaches as the scale of problems increases, the CO pipelines using our models offer an incremental performance improvement relative to a state-of-the-art MIP solver CPLEX. The proposed uncertainty-based primal heuristics provide 6-75% better optimality gap values and 45-99% better primal gap values for the 16x upscaled instances and brings immense speedup to obtain high-quality solutions. All these gains are achieved in a computationally efficient modeling approach without sacrificing solution quality.
Benzer Tezler
- Graf teori tabanlı ağ dizayn probleminin matematik programlama modeli ve optimizasyon algoritmaları
Mathematical programming model and optimization algorithms of graph theory based network design problem
SARA BADUR DALMAN
Doktora
Türkçe
2025
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEskişehir Osmangazi ÜniversitesiMatematik Bilgisayar Ana Bilim Dalı
DOÇ. AHMET FARUK ASLAN
PROF. DR. MUSTAFA BAYRAM
- Heterojen çizge sinir ağlarında kontrastlı öğrenme tabanlı öneri sistemi
Heterogeneous graph neural networks contrastive learning based recommender system
HALİL BERK DERGİ
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolTOBB Ekonomi ve Teknoloji ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BUĞRA ÇAŞKURLU
- Comparing the effectiveness of graph neural networks and machine learning algorithms for fNIRS-based neuromarketing research
FNIRS tabanlı nöropazarlama araştırmalarında çizge sı̇nı̇r ağları ile makı̇ne öğrenimi algorı̇tmalarının karşılaştırılması
ATAKAN GÜNGÖR
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMEF ÜNİVERSİTESİBilişim Teknolojileri Ana Bilim Dalı
DR. ÖĞR. ÜYESİ TUNA ÇAKAR
- Graph neural networks as surrogate models for structural analysis: A study on buckling behavior
Yapısal analiz için vekil modeller olarak grafik sinir ağları: Burkulma davranışı üzerine bir çalışma
ÖMER KURT
Yüksek Lisans
İngilizce
2025
Makine MühendisliğiOrta Doğu Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. ULAŞ YAMAN
- Graph neural networks on predicting aerodynamic flow fields around airfoils
Kanat kesitleri çevresindeki aerodinamik akış alanları tahmininde grafik sinir ağları
SÜLEYMAN ONAT ÇELTİK
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HANDE ALEMDAR
DOÇ. DR. ÖZGÜR UĞRAŞ BARAN