Graph neural networks-based primal heuristics for combinatorial optimization

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.