Graph attention network (GAT) based branching in combitorial optimization problems

Abstract

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. Supplementary code for this study can be found at https://github.com/GokhanMurali/learn2branchbyGAT.

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. Bu çalışmada kullanılan kod bloklarına aşağıdaki adresten ulaşmak mümkündür: https://github.com/GokhanMurali/learn2branchbyGAT