Transformer-Based Feature Learning for Algorithm Selection in Combinatorial Optimisation

This model learns the best algorithm for a given instance. Learning is modelled as a multi-class classification task where the assigned class is the best algorithm. The final activation function is SoftMax, which generates a probability distribution over all the algorithms in the portfolio, where a higher probability indicates a higher likelihood to be the best. SoftMax activation is well suited to associating the highest probability to one best algorithm.

Learning one best algorithm is restrictive when multiple algorithms perform similarly well. The C-NN model thus learns the competitiveness of the algorithms in the portfolio. We consider an algorithm competitive if it solves an instance in under ten seconds or less than double the time taken by the best algorithm for that instance. Hence, multiple algorithms may be deemed competitive. We propose to model learning as a multi-label classification task where each algorithm is associated with a competitiveness fraction. The final activation function is Sigmoid, which yields a probability per algorithm, and is well suited to our purpose: there could be multiple equally competitive algorithms and the competitiveness probability of one algorithm is uncorrelated with that of the others. We refrain from using SoftMax activation with the top $k$ competitive algorithms, as the number of competitive algorithms is not fixed. Imposing a fixed value of $k$ may constrain the model when the actual number of competitive algorithms exceeds $k$, and may lead to incorrect representations when it is fewer than $k$.

The two models share the same architecture, differing in their final activation function. The probability values in their output will be part of the extracted features for AS (as described in Section 4.2). The common part of the models (referred to as core) is composed of three components: (i) Transformer Encoder, (ii) Feature Elaborator, and (iii) Output Layer. Increasing the depth of the network by incorporating multiple layers with different objectives enhances the learning process [53].

Transformer Encoder transforms input instance text into a feature vector describing its semantic meaning without any pre-processing. The encoder is based on the BERT-base-uncased [20] architecture and shares hyper-parameters with the original except an increased input size (2048 tokens instead of 512) to support large textual input. Our choice of architecture is motivated by several factors. First, it has been successfully applied to classification tasks [46], making it a strong candidate for our purposes. Second, since we do not employ a pre-trained model, BERT shares the same architecture as RoBERTa [40]. Third, although architectures such as Longformer [9] offer a larger context window and more parameters, they are also more computationally expensive, and our preliminary experiments did not demonstrate any clear advantage.

Feature Elaborator passes the feature vector from the Transformer Encoder through two layers and the corresponding activation functions to project the features into the desired dimension. The Feature Layer is a linear layer that condenses the feature vector, mitigating the risk of dimensionality issues in subsequent non-neural ML applications (curse of dimensionality) [17]. Tanh activation replicates the last activation function of the BERT Transformer Encoder on the reduced feature vector. Its output will be part of the extracted features for AS (as described in Section 4.2). Post-Feature Layer is a linear layer that up-projects the feature vector, allowing the model to further elaborate the features avoiding underfitting [47]. Relu activation introduces non-linearity on the up-projected vector to facilitate learning.

Output Layer operates on the features to predict a floating point score per algorithm in the portfolio (referred to as Raw output). The final activation functions of B-NN and C-NN transform raw output into probabilities to better interpret it.

Car Sequencing [22] involves scheduling the production of a set of cars, each potentially requiring different optional features. The production line is divided into stations, each responsible for installing a particular option (e.g., air conditioning, sunroofs). Figure 2(a) shows the parameter and decision variable declarations in an Essence model. It defines three integer parameters: n_cars, n_classes, and n_options, from which domains Slots, Class, and Option are derived. Further parameters refine the problem: quantity, mapping each class to the number of cars required; maxcars, mapping each option to the maximum number of cars allowed in any consecutive block; blksize, a function mapping each option to the size of each consecutive block; and usage, a relation indicating which classes require which options. A decision variable with an abstract domain, car, maps from production slots to classes.

The problem contains a single top level constraint. This constraint uses a sliding-window mechanism to control the distribution of options along the car sequence. For each option, it defines a window of consecutive car slots whose length is the sum of the maximum allowed cars with that option and an additional block size delta. Within every such window, the total number of cars requiring the option must not exceed the allowed maximum. This ensures that the usage of each option is evenly distributed, preventing any clustering that could overload production capabilities.

We use 10,214 car sequencing instances.

Covering Array [30] originates from hardware design. A covering array CA$(t,k,g)$ of size $b$ is a $k\times b$ array over $\{0,\mathrm{\dots },g-1\}$ in which every $t$-way combination of row indices and values appears in at least one column. The smallest such $b$ is called the covering array number, CAN$(t,k,g)$. We use the decision version of the problem (Figure 2(b)). The input parameters of the model are: t, the strength, k, the rows, g the array’s values domain, b the number of columns of the covering array. The decision variable is CA: an integer-indexed matrix of integer values in the range 1 to g.

The first constraint in this model requires that for every strictly increasing sequence of $t$ rows, every possible combination of $t$ values (from the $g$ available) is represented in at least one column of the matrix CA. This guarantees that the matrix forms a covering array of strength $t$. The remaining two constraints are for symmetry breaking.

We use 2,236 instances for this problem.

Social Golfers [54] involves scheduling golfers in $g$ groups of size $s$ for $w$ weeks, such that no pair of golfers meets more than once. Figure 2(c) shows the parameter and decision variable in an Essence model of the problem. An unnamed type, Golfers, represents all the golfers in the schedule, with size $g\times s$. The decision variable, sched, is a set of partitions, each corresponding to a week’s grouping of golfers.

The only constraint in this model is that of socialisation: it ensures that any two distinct golfers are paired together in the same group in at most one week. For every pair, it sums a Boolean indicator (converted to an integer) across all weeks, with each indicator signalling whether the pair played together in that week. The total for each pair is constrained to be no more than one, ensuring that no pair of golfers is scheduled to play together more than once over the course of the $w$ weeks.

We use 1,039 instances for this problem.

Car Sequencing has three models based on two representations for the car decision variable and the usage parameter. The car variable can be represented as either a one-dimensional array of integers or a two-dimensional Boolean array, while the usage parameter can be either a Boolean array or a set of tuples. Model $M_1$ uses a one-dimensional array for car and a set of tuples with a table constraint for usage. Model $M_2$ uses a one-dimensional array for car with a Boolean array for usage and the element constraint. Model $M_3$ uses a two-dimensional Boolean array for car and a set of tuples with a table constraint for usage.

Covering Array has one model $M_1$ because the problem is expressed with a single matrix decision variable, and matrix variables map directly to Essence Prime. The constraints likewise do not permit additional variations.

Social Golfers has four models offering different matrix-based encodings of the weekly partitions. Model $M_1$ uses a single 3D matrix indexed by $\text{weeks}\times \text{groups}\times \text{slots}$, where each entry is an integer indicating which golfer is in a particular part of the partition for a particular group and week. $M_2$ uses a 3D Boolean matrix, indexed by weeks, groups, and golfers, to indicate whether a given golfer is in a specific part of the partition. $M_3$ splits the partitioning into multiple matrices, capturing information such as the number of parts, which golfer goes into each position, and how many slots are used in each group. By breaking down the partition into several matrices, this approach can exploit different constraint formulations within the same overall representation. $M_4$ combines two matrix encodings: one stores explicit integer assignments for each slot and another tracks membership via Booleans.

We use Kissat [10], a SAT solver; Chuffed [15], a CP solver with lazy clause generation; CPLEX [29], a commercial MIP solver; and OR-Tools CP-SAT [21], a hybrid solver combining clause learning, CP-style propagation, and MIP-based methods. We interface to these solvers via Savile Row [42].

Car Sequencing uses a portfolio of 12 algorithms derived from the combination of three Essence Prime models and four constraint solvers. Figure 3(a) (top) shows the PAR10 scores for these algorithms, evaluated across the entire instance set. A key observation from Figure 3(a) (top) is the lack of a dominant model or solver: there is no algorithm with the same behaviour as VBS, meaning that no algorithm is the “best” on each instance. The algorithms, excluding those involving $M_3$, which always underperform independently of the solver, exhibit diverse performance characteristics. Notably, the gap between the VBS and the SBS algorithm ($M_2$-Chuffed) is significant, with the SBS achieving only 0.01% of the VBS’s performance. This underscores the potential for AS to leverage complementary strengths among algorithms. Figure 3(a) (bottom) shows the average competitiveness (as the percentage of the instances where the algorithm is competitive). All algorithms are competitive on some instances, except $M_2$-CPLEX, which was the worst overall algorithm. It is typically very difficult for an AS method to always select the best algorithm for a given instance. At the same time, this may not always be necessary, as competitive algorithms could also do well on the instance.

We can see that even though $M_2$-Chuffed appears to be the best overall algorithm in Figure 3(a), it is the winner on a fairly small number of instances according to plot of Figure 4(a). Instead, $M_1$-CPLEX, $M_1$-Chuffed and $M_1$-OR-Tools have significantly higher numbers of instances where they win. These three algorithms, which are also the top three competetive algorithms according to Figure 3(a) (bottom), cover a significant part of the instance space.

Covering Array has one Essence Prime model, hence four different algorithms combining the model with the four solvers. Figure 3(b) (top) shows PAR10 scores of each algorithm in the full instance set. Contrary to Car Sequencing, for this problem class the gap between SBS and VBS is much smaller. With $M_1$-Kissat being the SBS, VBS as a fraction of SBS is 0.72. In terms of competitiveness (bottom figure), we can see that $M_1$-Chuffed and $M_1$-Kissat are almost always competitive, $M_1$-CPLEX is competitive around 60% of the time and $M_1$-OR-Tools roughly 50% of the time. This second view shows a different story from the top figure where $M_1$-Kissat seems to be the clear winner. This suggests a much more complex instance set where AS could take advantage of the different algorithms.

Even though the gap between SB and VBS is much smaller compared with the Car Sequencing case, Figure 4(b) shows that each algorithm contributes to VBS, even $M_1$-CPLEX which has the worst PAR10 score. $M_1$-OR-Tools is the least contributing algorithm while $M_1$-Chuffed and $M_1$-Kissat, the main competitive algorithms according to Figure 3(b) (bottom), both contribute similarly to VBS, with $M_1$-Kissat contributing slightly more than 50% of the time and $M_1$-Chuffed roughly 45% of the time.

Social Golfers has four Essence Prime models, resulting in sixteen different algorithms in conjunction with the four solvers. The PAR10 scores of Social Golfers (Figure 3(c), top) differ from those of the previous problems: 6 algorithms dominate all the others with similarly bad results. The algorithms including the models $M_1$ and $M_2$ have the best performance when coupled with Chuffed, Kissat and OR-Tools. The same cannot be said for CPLEX because it performs similarly to the other algorithms. The gap between SBS and VBS is in the middle between Car Sequencing and Covering Array since VBS as a fraction of SBS is 0.65. $M_1$-Chuffed, $M_1$-Kissat, $M_1$-OR-Tools, $M_2$-Chuffed, $M_2$-Kissat and $M_2$-OR-Tools are the only competitive algorithms more than 10% of the time (Figure 3(c), bottom). This may seem less than ideal. However, the gap between SBS and VBS shows that whenever $M_2$-Kissat is not the best algorithm it is worse by a considerable margin, motivating AS.

The participation to VBS, in Figure 4(c), shows that, although $M_2$-Kissat is the SBS, $M_2$-Chuffed is the algorithm that contributes by far the most to VBS while $M_2$-Kissat wins only in a handful of instances. This is a clear indication of the potential of AS for this problem class.

We conclude that each problem in our case study, along with its set of instances and algorithm portfolio, serves as a suitable candidate for evaluating our methodology.

Each AS approach is evaluated using PAR10 across 10-fold cross validation. In each fold, $10\%$ of the training data serves as a validation set to support neural network training and hyper-parameter optimisation. We use the same computer configuration as in  Section 5.3 for the CPU-based experiments, while GPU is used for neural network training and inference, as detailed below. In the hybrid approaches, we make use of K-means and AutoFolio for the AS task. We tested the number of clusters in K-means in the range [2,21] and chose that which resulted in the lowest validation PAR10 score. AutoFolio is an AS framework that offers a tuning mode with its own hyper-parameter configuration space. The tuning is done using the hyper-parameter optimisation tool SMAC [28], which we employ with a single CPU core and a tuning budget of $5$ hours.

All NN models are implemented using PyTorch [7] and trained from scratch on a GPU equipped with an NVIDIA A5000 accelerator. The Adam optimiser [32] is employed for all training processes. Model hyper-parameters, including the learning rate, (mini-)batch size, and number of epochs, are selected based on a combination of computational resource constraints and manual experimentation. The final hyper-parameter values are detailed in Appendix A. Cross Entropy is applied in the B-NN models, while Binary Cross Entropy is used in the C-NN models. In addition to the fold mechanism used as a precaution against overfitting, we monitor the validation loss during training and retain the model with the lowest validation loss to further reduce the risk of overfitting.

Due to the different scales of PAR10 across folds, following the existing AS literature [38], we define the normalised score as $(p(AS)-p(VBS))/(p(SBS)-p(VBS))$, where $p(AS)$, $p(VBS)$ and $p(SBS)$ are the PAR10 scores of an AS approach, the VBS, and the SBS on the same fold, respectively. VBS has a score of 0 while SBS has a score of 1. We want to minimise the normalised score. Feature extraction time is included in all PAR10 calculations unless its exclusion is mentioned explicitly. An AS approach is considered effective if its normalised score is less than $1$, i.e., it performs better than SBS – the AS approach without any learning required.