Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks

Graph neural networks are usually treated as auxiliaries for combinatorial optimization: they imitate algorithms, guide search, or supply scores to classical procedures. We show that this auxiliary role is not intrinsic. A GNN can itself be a heuristic. For the Euclidean Travelling Salesman Problem, we train a non-autoregressive GNN with no labels, rewards, sequential decoding, search, or local improvement. A differentiable Hamiltonian-cycle objective is the only supervision. The trained model produces a complete tour in one forward pass, while dropout and snapshots from a single training trajectory provide solution diversity without engineered moves. The heuristic is therefore learned, not programmed. It is also fast: batched inference remains in the millisecond regime on GPUs. Experiments on TSP100, TSP200, and TSP500 show that the model consistently improves over nearest-neighbor greedy baselines. These results identify unsupervised GNNs as a class of fast learned heuristics for combinatorial optimization.

Automated Algorithm Selection (AS) aims to improve problem-solving performance by selecting, for each problem instance, the most suitable algorithm from a predefined portfolio. This is particularly relevant to the Traveling Salesman Problem (TSP), where solver performance is strongly instance-dependent. We introduce GNNAS-TSP, a Graph Neural Network (GNN)-based AS framework that learns TSP instance representations directly from raw graph data, avoiding manual feature engineering. GNNAS-TSP formulates AS as a joint cost-prediction and ranking task. We evaluate cost-based (mean squared error (MSE), mean absolute error (MAE), and Huber), rank-based (RankNet, ListNet, and LambdaRank), and hybrid learning objectives for a portfolio comprising Chained Lin-Kernighan, Edge Assembly Crossover, Lin-Kernighan-Helsgaun, Multiagent Optimization System, and Concorde. Experiments use fixed computational budgets of 10 and 60 seconds. On the held-out test set, the selected configurations improve on the Single Best Solver (SBS) in normalized solution cost at both budgets. For the 10s budget, AS achieves substantial and statistically significant cost improvement over SBS. Overall, the results suggest that GNNAS-TSP is a useful meta-solving strategy when exploitable variation exists across solver performance.

Although the Maximum Clique Problem (MCP) has been extensively studied and features a rich ecosystem of exact solvers, empirical evidence shows that solver performance varies substantially across graph families. Consequently, selecting an appropriate algorithm for a given instance remains an open and practically important challenge that has received little systematic attention. We address this gap by developing an instance-aware selection framework that systematically combines global statistical descriptors with learned topological representations. We construct a comprehensive benchmark by evaluating four state-of-the-art exact solvers on a diverse collection of graph instances and deriving both global statistical and local structural features. An evaluation of conventional classifiers establishes Random Forest as a strong baseline and reveals that connectivity and topological features are key predictors of performance. Motivated by these observations, we introduce a dual-channel architecture that jointly leverages a Graph Attention Network for capturing local neighborhood patterns and a Multilayer Perceptron for modeling global statistical features. Extensive experiments show that the proposed dual-channel model consistently surpasses classical baselines and the single-best solver, achieving 90.43% test accuracy. These findings demonstrate the value of integrating local topological encoding with global statistical cues for combinatorial algorithm selection. Code and models are available at: https://anonymous.4open.science/r/GAT-MLP-7E5F.