# Addressing the Algorithm Selection Problem through an Attention-Based Meta-Learner Approach
## 1 Introduction  
Given the nature of NP-hard combinatorial optimization problems, the search space grows exponentially with the number of inputs. Thus, it is unfeasible to employ exact methods, except for in small cases [1]. Instead, approximation techniques, such as heuristics, produce solutions for larger instances (although they cannot guarantee the optimality of such solutions) [2, 3]. Moreover, we now understand that no single algorithm will yield the best performance in all instances of a problem [4]. However, an \"intelligent\" technique may benefit from considering the structure of the problem at hand [5]. Consequently, a new problem arises: selecting the most appropriate algorithm for a particular problem instance, a task formally known as the algorithm selection problem (ASP) [6, 7]. A recent approach to this problem involves machine learning to identify the patterns between problem instances and algorithms by leveraging the meta-features that characterize such problem instances [6, 8]. Thus, we must face the challenge of deciding the performance model and the type of machine learning technique to use. This work investigates attention-based neural networks as an alternative performance mapping mechanism within the algorithm selection framework. The architecture used issimilar to the encoder from the transformer by [PERSON] et al. [9], a neural network architecture that leverages the attention mechanism for modeling long-term dependencies in data. This work aims to prove that attention-based neural networks can select the best algorithm for a given problem instance offline. Then, we can state that these neural networks constitute an effective alternative to learning performance mappings from problem instances to algorithm space. The rationale behind our proposal is to leverage the attention mechanism, specifically using multiple attention heads to differentially weigh the importance of the features that characterize the problem instances [9]. We decided to use multi-head attention instead of a single attention head so that multiple positions can be jointly attended [10] and leverage the specialization among attention heads that the approach encourages [11]. Moreover, this investigation is conducted in the context of the vehicle routing problem with time windows (VRPTW) [1], which aims to find a collection of routes covering a set of customers, all of them starting and ending at a depot and within a specific time interval referred to as the time window [1]. Additionally, it is relevant to note that this work focuses not on the application problem, i.e., the VRPTW, but on showing how attention-based neural networks are competent algorithm selectors. Consequently, we do not aim to beat the state-of-the-art solvers for the VRPTW. Instead, our objective is to show that the proposed attention-based model, when compared against other common approaches found in the literature, consistently chooses the best algorithm to solve a particular problem instance which, in this case, happens to be a VRPTW instance. Nevertheless, we assume these results should be generalizable to other problem domains. Although recent advances in neural network architectures and techniques have led to significant performance improvements in many domains [12; 13; 14; 15; 16], the literature related to using neural networks to select meta-heuristics for solving combinatorial optimization problems has mainly relied on simple multi-layer perceptrons (MLPs) [17; 18; 19; 20], with many studies using the one hidden layer architecture implemented in the WEKA data mining software [21]. With this in mind, we define our main contribution as the proposal of an attention-based neural network as a meta-learner for selecting meta-heuristics (in this particular case, tested on three different SA configurations) for solving the VRPTW.