Neural Combinatorial Optimization

Ask about this topic

Overview

Neural combinatorial optimization studies how learned models can construct, improve, or guide solutions to problems with many discrete choices and hard constraints, including vehicle routing, scheduling, packing, and graph optimization. Common approaches include graph neural networks and Transformers trained with supervised examples from solvers, reinforcement learning, self-supervised objectives, and newer diffusion or preference-based methods. Many systems combine learned policies with classical search, local improvement, or exact optimization to improve feasibility and solution quality. A central challenge is whether they generalize to larger or unfamiliar instances and offer a practical advantage over strong classical heuristics when training and inference costs are counted.

Latest papers

CardsList

137 papers17 papers in the last four weeks, up 113% on the four weeks before. 0.1% of all new papers.

Aug 14, 2026

JAMPR+/L2D: scalable neural heuristic for constrained vehicle routing problems in dynamic environment

The vehicle routing problems with real-world constraints (we consider vehicles capacity limits, time windows constrains, pickup-and-delivery multi-depo --- CPDPTW) pose significant computational challenges. While classical exact and heuristic methods remain effective to solve problems of small/medium size (N≲100N\lesssim100), they often lack adaptability and scalability for larger logistics tasks. In this work, we show how JAMPR+/L2D RL deep learning model, proposed in to solve large CPDPTW problems can be adopted in the case of substantial changes of graph distance matrix. We test performance of JAMPR+/L2D model for medium-sized CVRP and VRPTW problems on CVRPLIB benchmarks: JAMPR+/L2D outperforms the state-of-the-art heuristic HGS in over 85% of instances, achieving improvement in objective gap. We show that the JAMPR+/L2D model trained on CPDPTW problem, generalizes well for tasks with simpler constraints (CVRP, VRPTW), for different problem sizes and for moderate changes in distance matrixes. For more substantial changes in distance matrixes, we propose here to make fast finetuning of JAMPR+: on ORTEC data (for CPDPTW) the proposed strategy remarkably reduces the objective gap without full model retraining, what will give both accuracy and rapid inference of the model in the practical routing scenarios with distance matrix changes.

Andrew Soroka, Alex Meshcheryakov

Moscow State University, Moscow, Russian Federation · Space Research Institute of RAS, Moscow, Russia

Vehicle RoutingNeural Combinatorial OptimizationRL for Combinatorial Optimization
AskPDF
Aug 14, 2026

Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases because of exponential complexity. We investigate the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and compare solutions obtaining by exact solver SCIP with heuristic algorithms such as LKH, 2-OPT, 3-OPT, the ORTools framework, and the deep learning model JAMPR. We demonstrate that for problem of size 50 deep learning and classical heuristic solutions became close to SCIP exact solution but requires less time. Additionally for problems with size 100, SCIP exact methods around 13 times slower that neural and classical heuristics with the same route cost and on around 50% worse for the first feasible solution on the same time. To conduct experiments, we developed the Smart Routes platform for solving route optimization problems, which includes exact, heuristic, and deep learning models, and facilitates convenient integration of custom algorithms and datasets.

Andrew Soroka, German Mikhelson, Alexander Mescheryakov +1

Moscow State University, Faculty of Computational Mathematics and Cybernetics, Moscow · Space Research Institute of RAS, Moscow

Vehicle RoutingMetaheuristic OptimizationNeural Combinatorial Optimization
AskPDF
Aug 13, 2026

Sampling Luck Masquerades as Allocation Gain: Auditing Test-Time Budget Allocation for Neural Combinatorial Optimization

Neural combinatorial optimization (NCO) solvers report the best of many sampled solutions per instance, and the sample count is, by convention, identical for every instance. Whether a non-uniform allocation of a fixed total budget would buy anything has not been measured. We measure it, and we audit the measurement itself. First, on in-distribution workloads the allocation headroom is not detectable. Across three pretrained solvers (POMO, AM, SymNCO) on uniform TSP-100, an oracle allocation computed and evaluated on the same stored samples reports a 2.2-2.6% gain with intervals excluding zero; measured out of sample the same gain is indistinguishable from zero (0.457, 0.015, -0.512 percent). Following the customary in-sample procedure, all three solvers would have supported a published 2%-level gain that does not exist. We calibrate this bias against an instance-wise null in which the true gain is zero by construction; over the ranges we test it does not shrink with more samples or more instances. Second, the same correction that removes the phantom gains preserves a real one. Under distribution shift (a workload mixing uniform and clustered instances), a pre-registered confirmatory experiment finds that allocation guided by held-out sample statistics improves best-of-k by 11.5% (AM, primary endpoint; 95% CI [7.4, 19.7]) and 12.0% (SymNCO, replication) at equal evaluation budget, with the signal-acquisition cost not charged; a pre-registered negative control (POMO, an order of magnitude more robust to shift) shows -0.3% [-0.7, 0.24]. The gain exceeds a frozen distribution-label baseline by 4.2 points [1.9, 7.7]. An exploratory policy charging a 20-sample probe against the same budget retains 3.4% (AM) and 4.6% (SymNCO). We give a correction procedure and a reporting checklist, and release all data, code, and the pre-registration record.

Jinhyung Bae

Department of Industrial and Management Engineering and the AI Data Convergence program, Hankuk University of Foreign Studies, Yongin, Republic of Korea

Algorithmic AuditingInference-Time Compute AllocationSelection BiasNeural Combinatorial Optimization
AskPDF
Aug 13, 2026

Constrained Graph Diffusion for Mixed Integer Optimization

This paper proposes a novel learning-based approach to approximately solve instances of mixed-integer optimization problems. These problems are computationally challenging, as they require jointly determining discrete and continuous decisions while satisfying complex combinatorial constraints. problem-agnostic and can accommodate a broad class of mixed-integer optimization problems through suitable projection operators. We introduce Constrained Graph Diffusion (CGD), a learning-based framework that approximately solves recurring instances of such problems by learning a conditional distribution over their discrete decisions. CGD uses a graph-based diffusion model and incorporates constraint information directly into the reverse diffusion process, steering intermediate predictions toward the feasible region throughout generation. By operating on continuous relaxations of the discrete variables, CGD defines a differentiable constrained generation pathway up to terminal discrete recovery. Once the discrete decision is recovered and fixed, a numerical optimizer solves the remaining continuous problem, avoiding online combinatorial search over the binary variables while retaining numerical optimization for continuous completion. We evaluate CGD on AC-OPF with branch switching and discrete portfolio optimization, demonstrating substantial improvements in feasibility and solution quality over learning-based baselines while achieving speedups of up to 543×543\times over state-of-the-art MIP solvers on large instances.

Vincenzo Di Vito, Yusuf Guven, Babak Badnava +3

University of Virginia · MIT · Los Alamos National Laboratory

Mixed-Integer Linear ProgrammingConstrained OptimizationNeural Combinatorial Optimization
AskPDF
Aug 12, 2026

SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization

Neural combinatorial optimization (NCO) relies on parallel solution sampling for training, yet existing methods fail to fully exploit the rich information latent in a co-sampled solution group. Preference-optimization methods anchor on the single best solution and discard fine-grained quality and structural signal from all other peers-a failure we term gradient signal polarization. Mean-based baselines instead weight peers uniformly, so structurally near-identical peers flood the baseline with redundant information and keep gradient variance high-a failure we term baseline redundancy. We propose SSPO (Structure-Aware Similarity-Weighted Preference Optimization), which scores all BB sampled solutions jointly through a dissimilarity-weighted leave-one-out baseline: structurally distinct peers receive higher weight, resolving both failures in a single mechanism. The baseline uses zero-parameter, problem-adaptive solution embeddings built from the encoder's existing node representations. Experiments on TSP, EFL, and JSP benchmarks show consistent gains over prior best-anchor and uniform-weight baselines. A direct comparison against uniform RLOO on TSP and EFL confirms that structure-aware weighting is the primary driver of improvement. The SSPO-trained EFL policy has been deployed in a production facility-location system at JD.\mathord{.}com, confirming practical viability at scale.

Yuanyu Li, Jintao Xu, Zijiang Liu +6

Supply Chain Tech Team Y, JD.com, Beijing, China · Department of Industrial Engineering, Tsinghua University, Beijing, China · Faculty of Engineering and Faculty of Business and Economics, The University of Hong Kong, Hong Kong, China

Combinatorial OptimizationPreference OptimizationImportance WeightingRL for Combinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Aug 10, 2026

DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning

Large traveling salesman problem (TSP) instances require a solver to allocate limited computation while preserving the validity of its outputs. Existing neural--operations-research (OR) hybrids predict guidance without requiring learned transitions to satisfy constraints discovered during search. DualCert introduces constraint-coupled learning, in which current degree equations and dynamically separated subtour-elimination constraints (SECs) define each learned transition. At each refinement, the degree equations and selected, strictly satisfied SEC equations, with positive slacks, define an iterate-dependent primal-slack Karush--Kuhn--Tucker (KKT) manifold. Repaired dual variables and violated SEC rows define a local cost field. An exact constrained mirror-descent step maps each finite state to a positive state on the same manifold. Where selected rows and deterministic ties remain fixed, implicit differentiation maps parameter perturbations into the manifold tangent space and reuses the forward constraint operator for the local-cost-field derivative. The terminal edge state allocates computation across Held--Karp ascent, candidate-graph edge tests, and tour construction under a fixed budget. Deterministic verification recomputes original costs and accepts only verified candidate-graph lower bounds and edge decisions. On 1,000 held-out TSP1000 instances, DualCert attains a mean tour-cost gap of 0.0573%0.0573\% from Lin--Kernighan--Helsgaun version 3 (LKH-3) reference tours in 9.559.55 batch-amortized seconds per instance. It returns a verified candidate-graph lower bound for every instance and achieves 81.46%81.46\% edge-decision coverage. The mean gap is 67.1%67.1\% smaller than the reported NeuroLKH mean gap. Thus, optimization constraints govern learning, while deterministic verification preserves output validity.

Yancheng Song, Yongzhi Qi, Wei Qi +1

Department of Industrial Engineering, Tsinghua University, Beijing 100084, China · JD.com, Beijing, China · College of Engineering, UC Berkeley, Berkeley, CA 94720, USA; Faculty of Engineering, Faculty of Business and Economics, University of Hong Kong, Hong Kong, China

Traveling Salesperson ProblemPrimal-Dual OptimizationConstrained OptimizationNeural Combinatorial Optimization
AskPDF
Aug 1, 2026

Neuro-Evolved Heuristics for Variable Gapped Common Subsequence Identification

This study addresses the Variable Gapped Longest Common Subsequence Problem (VGLCSP), a variant of the classical longest common subsequence problem with additional gap constraints and applications in sequence alignment and time-series analysis. While the two-sequence version has been widely studied using dynamic programming, the generalized multi-sequence form is usually solved with beam search-based heuristics, whose hand-crafted designs often lack robustness. To overcome this limitation, we propose a learning-based approach for automatically designing more effective data-driven heuristics. The heuristics are represented by a neural network with predefined architecture, whose weights are optimized by a genetic algorithm within a neuro-evolutionary framework. The learning process alternates between weight optimization and evaluation within an iterative multi-source beam search procedure, a state-of-the-art method for the problem. Rather than constructing solutions directly, the neural network learns to guide the search process, producing a neuro-evolved heuristic. We further introduce an ensemble heuristic that combines the scores of learned and the best-performing hand-crafted heuristic. Integrated into the iterative multi-source beam search framework, the resulting hybrid approach outperforms existing methods on both synthetic benchmark instances and newly introduced real-world instances with data-driven gap constraints.

Marko Djukanović, Christian Blum, Aleksandar Kartelj +2

University of Nova Gorica, Nova Gorica, Slovenia · Artificial Intelligence Research Institute (IIIA-CSIC), Barcelona, Spain · Faculty of Mathematics, University of Belgrade, Belgrade, Serbia +2

Automated Heuristic DesignNeural Combinatorial OptimizationNeuroevolution
AskPDF
Jul 31, 2026

Stabilized Best-of-KK Training for Neural Combinatorial Optimization

Leader Reward modifies POMO training to emphasize the best trajectory produced by repeated inference. We test a narrow extension: replace its binary leader/non-leader distinction with a stabilized rank signal indexed by a sampling budget KK. With the POMO architecture, 3,050-epoch schedule, and TSP-100 test set held fixed, the Leader Reward reimplementation obtains 7.76627.7662 under 100-start, 8-augmentation greedy decoding, matching the reported 7.7667.766 at its displayed precision. Under independent sampling, the stabilized K=8K=8 recipe lowers realized Best-of-8 cost in all three paired training seeds: 7.79447.7944 versus 7.81367.8136. This observation is estimation-only and decoder-specific: three seeds are below the six-seed testing floor, Leader Reward is better at sampled K=1K=1, and it remains slightly better under its original augmented-greedy protocol. We make no unbiased-estimator, universal superiority, or state-of-the-art claim.

Melveena Jolly, Midhun Xavier

1Independent Researcher

Traveling Salesperson ProblemBest-of-N SamplingCombinatorial OptimizationRL for Combinatorial OptimizationReward Design for RLNeural Combinatorial Optimization
AskPDF
Jul 31, 2026

Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization

Neural Combinatorial Optimization (NCO) techniques have emerged as a highly efficient alternative to traditional exact algorithms for solving routing problems such as the Traveling Salesman Problem (TSP). However, the generalization capabilities of these Reinforcement Learning-based models are severely hindered when scaling to high-dimensional instances. This issue has been mitigated in other domains, like computer vision and natural language processing, by adopting a self-supervised pre-training strategy. Nevertheless, its application to routing graphs, which lack complex topological attributes beyond 2D spatial coordinates, remains a challenge. In this paper, we propose a geometric self-supervised pre-training framework specifically designed to capture spatial invariance and global relative distance distributions. By applying isometric transformations, such as rotations and axial reflections, the model learns robust structural representations prior to the policy optimization phase. Empirical results demonstrate that this strategy consistently outperforms models trained from scratch (baselines), achieving a 7.23% improvement in tour length for massive zero-shot extrapolation scenarios (TSP1,000). Furthermore, the proposed model exhibits remarkable computational efficiency, delivering speedups of up to two orders of magnitude over the exact solver Concorde at massive scales. The source code and pre-trained models are publicly available at https://github.com/davidaguadocosano/TSP-GeoPretrain.git.

David Aguado, Daniel Fuertes, Carlos R. del-Blanco +1

Grupo de Tratamiento de Imágenes, Information Processing and Telecomunications Center, ETSI Telecomunicación, Universidad Politécnica de Madrid, 28040, Madrid, Spain

Traveling Salesperson ProblemSelf-Supervised LearningSelf-Supervised Pre-TrainingGeometric Representation LearningRL for Combinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Jul 30, 2026

LM-GRASP: Instance-Specific Language Models for Combinatorial Construction via Online Imitation Learning

Machine learning for combinatorial optimization typically relies on neural constructors trained via reinforcement learning on large offline datasets for a fixed problem class-incurring high pretraining costs and generalizing poorly outside the training distribution. We propose an alternative: a metaheuristic framework that reformulates the randomized constructive phase of GRASP as an online imitation learning task, trained from scratch on each problem instance. A local search procedure acts as an expert oracle, while a decoder-only Transformer serves as the constructive policy. Unlike classical GRASP, which relies on static, myopic heuristic rules based on localized scalar costs, our approach is fully data-driven: the construction policy emerges from high-quality solutions discovered during the search itself, with no problem-specific feature engineering required. We instantiate this as LM-GRASP, a hybrid metaheuristic following an iterative learn-infer-improve cycle, training the policy online via behavioral cloning on a dynamic archive of elite trajectories-no external data or offline pretraining needed. The pipeline interfaces with the domain solely through the objective evaluator used by local search. Evaluated on the Taillard PFSP benchmark (ta51-ta60), the most discriminating block due to half its optima being unknown, LM-GRASP outperforms GPU-GRASP by 28.4 makespan units on average-comparable to the gain from GPU acceleration over sequential execution (27.2 units), though with overlapping standard deviations. This suggests instance-specific, online-trained language models are a promising, practical alternative to hand-engineered constructors, especially for landscapes resistant to classical greedy construction.

Mohand Mezmaz, Grégoire Danoy

SnT, University of Luxembourg

Metaheuristic OptimizationCombinatorial OptimizationImitation LearningNeural Combinatorial Optimization
AskPDF
Jul 30, 2026

AutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimization

Combinatorial optimization problems (COPs) underpin many real-world decisions, but their exponentially large search spaces make high-quality solutions costly to obtain. Neural combinatorial optimization (NCO) learns fast construction policies, typically with reinforcement learning (RL), while preference-based NCO improves sample efficiency by learning from relative solution quality. However, existing preference objectives combine two distinct design choices in manually specified, one-size-fits-all formulations: what learning signal to extract from each solution pair and how to weight each pair relative to the sampled set. We present AutoPref, the first LLM-guided framework for automated preference-objective discovery in NCO. AutoPref factorizes the objective into a pairwise loss program, which defines the learning signal, and a set-aware weighting program, which determines each pair's relative contribution. Their composition forms a unified programmatic objective space containing existing preference objectives as special cases. To make its search tractable, we introduce a staged conditional search strategy with behavioral gates that filter inadmissible programs before short-horizon training and evaluation. Across TSP, CVRP, FFSP, and JSSP, AutoPref consistently outperforms strong hand-designed baselines across problem scales, demonstrating the benefits and scalability of automated objective discovery for NCO.

Shengda Gu, Kai Li, Xinyi Ke +3

C2DL, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences · Tencent AI Lab +1

Automated Algorithm DiscoveryPairwise Preference EvaluationPreference OptimizationNeural Combinatorial OptimizationPreference-Based RL
AskPDF
Jul 26, 2026

Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search

Humans often find good solutions to combinatorial optimization problems that are computationally hard even for advanced computer algorithms. In the Euclidean traveling salesman problems (TSP), people rapidly produce tours that are near-optimal, despite severe limits on time and computation. What makes a tour human-like, and how might such solutions be learned? Here we address these questions through a large-scale behavioral and computational investigation of human performance in Euclidean TSP. We sampled a broad space of TSP instances, collected human solutions, and compared them with neural policies based on Pointer Networks, which are recurrent neural networks with an attention-based pointing mechanism that define probability distributions over valid tours. We trained these networks under multiple objectives, including reinforcement learning (RL), supervised learning from optimal tours, supervised learning from human tours, and RL fine-tuning after optimal-supervised pretraining. Human tours were not identical to optimal tours, but occupied a near-optimal geometric basin: they shared many structural properties with optimal solutions while preserving systematic human-specific deviations. The best account of human tours was not direct imitation of optimal tours, but a model pretrained on optimal tours, fine-tuned by RL, and decoded through Best-of-N\text{Best-of-}N sampling. These findings suggest that human-like solutions may emerge from a combination of structured supervised learning, RL, and test-time search, echoing computational principles underlying many modern artificial intelligence systems.

Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang +1

Department of Psychology, The University of Warwick, Coventry, United Kingdom. · Department of Psychology, The University of Hong Kong, Hong Kong, China. · Department of Psychology, The Chinese University of Hong Kong, Hong Kong, China. +2

Traveling Salesperson ProblemInference-Time SearchCombinatorial OptimizationImitation LearningRL for Combinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Jul 26, 2026

Learning to Optimize: Joint Routing and Flow Allocation on Sparse Non-Euclidean Networks

We study an integrated pickup-and-delivery problem on sparse, non-Euclidean networks that jointly optimizes cyclic routing, cargo flow allocation, and cross-cycle service. The tight coupling of these operational constraints creates a complex discrete-continuous decision space with highly restricted feasible regions. To overcome these computational challenges, we propose Double-Channel Graph Attention (DCGA), an end-to-end reinforcement learning framework. DCGA isolates network reachability and demand-service logic into separate graph channels and constructs valid routes using a simulator-coupled, constraint-informed decoder. Experiments on LinerLib benchmarks demonstrate that DCGA achieves seconds-level inference and delivers state-of-the-art solution quality on instances beyond a specific scale, with its advantage over existing baselines widening significantly as problem size increases. Supported by extensive stability and ablation analyses, our results demonstrate that this structure-aware learning approach provides an effective, low-latency engine for realistic routing-and-flow optimization.

Haomiao Sun, Fang He, Congyuan Ji +1

Department of Industrial Engineering, Tsinghua University, Beijing 100084, P.R. China · School of Management Science and Engineering, Central University of Finance and Economics, Beijing 100081, P.R. China

Graph Attention NetworksLearning to OptimizeCombinatorial OptimizationRL for Combinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Jul 24, 2026

Integrated Order Dispatching and Routing for Last-Mile Pickup via Deep Reinforcement Learning

In recent years, the growing complexity of last-mile pickup operations has increased the need for fast and accurate decision-making on logistics platforms. This challenge is fundamentally driven by two key and tightly coupled decision-making processes: order dispatching and routing. Solving them separately overlooks their interdependence, while fully end-to-end learning can be unstable and costly on large, variable-scale instances due to sparse rewards. To solve this problem, we propose an integrated optimization framework which couples a learned routing oracle with real-time dispatching heuristics. For the routing subproblem, we develop a Dynamic-Residual Graph Attention Network encoder with a Look-Ahead Courier-Personalized decoder. For the dispatching subproblem, we develop a routing-oracle-guided dispatching heuristic with local search, where the oracle provides near-optimal solutions to select candidate couriers while retaining real-time scalability. Extensive experiments on real-world datasets from Cainiao Logistics are used to test the performance of our approach, including an offline evaluation and an online rolling-horizon simulation. The experimental results show that our approach outperforms other benchmarks regarding solution quality and solving time, indicating it can effectively support logistics companies in solving real-time and large-scale last-mile pickup problems.

Yida Xu, Zhaofang Mao, Yuheng Miao +2

College of Management and Economics, Tianjin University, Tianjin 300072, China · Laboratory of Computation and Analytics of Complex Management Systems (CACMS), Tianjin University, Tianjin 300072, China

Vehicle RoutingSupply Chain ManagementRL for Combinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Jul 21, 2026

On the Effectiveness of Pretraining for Graph Combinatorial Optimization

This paper introduces a self-supervised pretraining framework for graph combinatorial optimization specifically designed to address the nature of routing problems like the Traveling Salesman Problem. By utilizing graph contrastive learning with geometric augmentations (specifically, rotations and axial reflections) the model is forced to learn invariant structural representations and global relative distance distributions. Results demonstrate that this pretraining strategy outperforms non-pretrained models across various problem scales. Notably, the hybrid strategy (combining rotation and reflection) achieved a 6.57% improvement in tour length for TSP1000, proving that geometric pretraining is an important inductive bias for effectively scaling neural solvers to high-dimensional instances.

David Aguado, Daniel Fuertes, Carlos R. del-Blanco +1

Grupo de Tratamiento de Imágenes, Information Processing and Telecomunications Center, ETSI Telecomunicación, Universidad Politécnica de Madrid, 28040, Madrid, Spain

Traveling Salesperson ProblemSelf-Supervised Pre-TrainingCombinatorial OptimizationGraph Contrastive LearningNeural Combinatorial Optimization
AskPDF
Jul 21, 2026

Enhancing Transformer-based Routing by Encoding Distance via Relative Positional Encoding

This paper explores Relative Positional Encoding (RPE) as an additive bias in Transformer architectures to solve the Team Orienteering Problem. By embedding in the attention mechanism pairwise spatial relationships among nodes of the graph that represents the routing problem, the transformer encoder can compute a richer spatial-aware graph embedding that allows the decoder to estimate better routes. Experimental results involving instances up to 100 nodes demonstrate consistent improvements in collected rewards and optimality gaps over vanilla Transformer architectures used by other state-of-the-art works. These findings highlight that explicit relational modeling significantly enhances scalability and generalization for complex combinatorial optimization.

Leyre Encío, Daniel Fuertes, Carlos R. del-Blanco +1

Grupo de Tratamiento de Imágenes, Information Processing and Telecomunications Center, ETSI Telecomunicación, Universidad Politécnica de Madrid, 28040, Madrid, Spain

Relative Positional EncodingCombinatorial OptimizationPositional EncodingGraph TransformerNeural Combinatorial Optimization
AskPDF
Jul 20, 2026

LaT: LLM-as-Trainer for Multi-Task Vehicle Routing Solvers

Multi-task neural solvers aim to handle multiple Vehicle Routing Problem (VRP) variants within a unified model, avoiding separate training for each constraint combination. However, VRP variants differ in optimization difficulty, while existing methods lack stage-wise feedback on their training status, making the model biased to some specific variants. Although meta-learning can support adaptive training, it typically requires bi-level optimization and additional gradient updates, increasing computational cost. To address this limitation, we propose LLM-as-Trainer (LaT), a plug-and-play training paradigm that uses a pretrained large language model as an external trainer. LaT periodically analyzes cross-task validation metrics to generate a stage-wise guidance vector. This vector is combined with the current task's constraint vector and injected into each encoder layer, providing the neural solver with additional training information during subsequent policy optimization. Experiments on 16 VRP variants show that LaT improves the solution quality of several state-of-the-art multi-task neural solvers on both trained and unseen variants, supporting the effectiveness and generality of the proposed training paradigm.

Yang Wang, Ya-Hui Jia, Wei-Neng Chen +3

School of Future Technology, South China University of Technology, China · School of Computer Science and Engineering, South China University of Technology, China · School of Engineering and Computer Science, Victoria University of Wellington, New Zealand +2

Large Language Model-Guided OptimizationMulti-Task LearningVehicle RoutingNeural Combinatorial Optimization
AskPDF
Jul 17, 2026

Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

Oscillatory Neural Networks (ONNs) present an attractive physics-based computing paradigm rooted in the dynamics of a network of typically fully coupled oscillators aiming to minimize an underlying energy function. In this paper, we propose an ONN-based solver for one well-known constrained combinatorial optimization problem, namely a Sudoku, by formulating the problem as a Graph Coloring problem. By modifying the already existing Graph Coloring solver to a computationally cheaper version and introducing an additional term ensuring the fulfillment of the Sudoku constraints, our solver is shown to significantly outperform the existing HNN- and ONN solvers in terms of accuracy. In particular, we are able to achieve nearly flawless accuracies on 4×44 \times 4 as well as rather high accuracies on 9×99 \times 9 Sudoku puzzles for different numbers of unknown digits.

Filip Sabo, Aida Todri-Sanial

NanoComputing Research Lab, Electrical Engineering Department Eindhoven University of Technology Eindhoven, the Netherlands

Sudoku SolvingOscillatory Neural NetworksCombinatorial OptimizationConstraint SatisfactionNeural Combinatorial Optimization
AskPDF
Jul 13, 2026

Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems

Learning-based methods for the traveling salesman problem (TSP) are often evaluated through the tours produced after decoding or search, but the learned object itself frequently lives in a surrogate space such as heatmaps, assignments, construction policies, or search-guidance scores. This hides the fundamental question: what Hamiltonian structure has actually been learned before decoding? In this study, we directly answer this question by learning TSP through a structurally meaningful latent object, rather than leaving most of the Hamiltonian structure to the final decoding stage. Based on a connected-by-construction rooted 11-tree Gibbs family, we propose an end-to-end unsupervised learning pipeline called C2TSP. The pipeline learns residual edge perturbations from unbiased TSP cost through implicit differentiation. For structural correction, a smoothed Held--Karp layer restores expected degree balance, while certificate-guided sharpening further pushes the connected distribution toward more tour-like structures. Experiments show that C2TSP yields strong decoding performance while preserving interpretable structural information. Ablations further verify that edge perturbation and certificate-guided sharpening jointly improve both tour cost and tour-like structure.

Ke Sun, Xinyuan Zhang, Xinwu Qian

Department of Civil and Environmental Engineering, Rice University, Houston, TX

Traveling Salesperson ProblemCombinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Jul 5, 2026

Two Black Boxes, One Solver: Encoder Probing and Decoder Attribution for Neural Multi-Attribute VRP under Hard-Mask and Recourse Decoders

Neural autoregressive solvers for the Multi-Attribute Vehicle Routing Problem (MAVRP) reach competitive cost but offer no per-step justification, a problem when dispatchers must validate, accept, or compare them. We open two complementary black boxes in one protocol. On the encoder side, linear probes, spontaneous-organization metrics, rank-based richness measures, and discovered-direction analyses with intervention validation characterize how the latent represents constraint families at the graph, node, and edge level. On the decoder side, three attribution methods (gradient, integrated gradients, DeepLIFT) feed three reading angles: abductive, contrastive against the best feasible alternative, and counterfactual (smallest input change that switches the action or restores feasibility). Explanations are scored on fidelity, concentration, stability, sanity, and actionability. Across six variants combining three encoders (Attention baseline, Unimp, UnimpMoe) with two decoders (Hard-Mask, Recourse), we find that graph inductive bias improves both representational predictability and decoder sanity, that the Mixture-of-Experts encoder represents constraints in a distributed rather than axis-aligned way, and that the Recourse training regime, not merely its softer mask, produces policies that represent infeasibility usefully, exposing make-feasible counterfactuals that Hard-Mask policies fail to produce even when fed infeasible alternatives externally.

Sohaib Afifi

Univ. Artois, UR 3926, Laboratoire de G´enie Informatique et d’Automatique de l’Artois (LGI2A), F-62400 B´ethune, France

Gradient-Based AttributionCounterfactual ExplanationsVehicle RoutingNeural Network InterpretabilityRepresentation ProbingNeural Combinatorial Optimization
AskPDF
Jul 4, 2026

TSP with Predictions: Heatmap to Tour with Provable Guarantees

The Traveling Salesperson Problem (TSP) has long served as a benchmark for evaluating the strength of optimization techniques in the classical theory of algorithms. In recent efforts to apply ML to algorithmic problems, TSP has also become a natural testbed for the development of ML-based techniques. A common approach is to train a neural network to output a heatmap estimating the likelihood of each edge to be part of the optimal tour; however, converting such a heatmap into an actual tour remains a non-trivial and often computationally intensive step. In this work, we propose algorithms for transforming heatmaps into tours with theoretical guarantees linking the achieved approximation ratio to the quality of the provided heatmap. In the spirit of algorithms with predictions, our results can be described as (1+2ηOPT)(1+2\fracη{\mathrm{OPT}})-approximation algorithms, where ηη denotes the L1 distance between the prediction (heatmap) and an optimal solution (tour). Since the previous works lack such explicit guarantees, we compare our approach against them experimentally.

Marek Eliáš, Fabrizio Grandoni, Adam Polak +1

Traveling Salesperson ProblemCombinatorial OptimizationLearning-Augmented AlgorithmsApproximation AlgorithmsNeural Combinatorial Optimization
AskPDF
Jul 3, 2026

SeqGPT: A Constrained Transformer Agent for the Inverse Designof Multi-Panel Composite Structures

Optimizing composite stacking sequences to match continuous targets (e.g., Lamination or Buckling Parameters) with discrete manufacturing constraints represents a challenging combinatorial inverse problem that regularly occurs in composite design especially when numerical optimization approaches are used (bi-step, bi-level configurations). In multipanel configurations, this complexity is further intensified by blending, a global compatibility/continuity requirement between the different panel stackings. This study presents SeqGPT, a conditional Transformer agent developed to replace computationally expensive iterative methods. To ensure both global continuity and manufacturing feasibility by construction, we implemented a hybrid neurosymbolic decoding strategy. SeqGPT predicts a conditional distribution that guides a Constrained Beam Search, where any branch violating blending rules is strictly pruned. Numerical experiments on the 18-panel horseshoe benchmark demonstrate that SeqGPT generates solutions near-instantaneously with buckling performance comparable to evolutionary methods, offering a significant speed-up compared to the state of the art.

Driss Chraibi, Alejandro García Pis, Stéphane Grihon +1

Toulouse INP · Airbus Operations SAS, Toulouse, France · IRIT +1

Materials ScienceNeural Combinatorial OptimizationInverse Design
AskPDF
Jul 1, 2026

Neural Certificate Pricing for Combinatorial Optimization Problems

Combinatorial optimization (CO) problems are difficult because certifiable discrete structure induces exponential search. One needs to search over the set exponentially many candidates to certify optimality, however, the structural feasibility of a path, packing, or cover can be verified in polynomial time once supplied. In this study, we introduce Neural Certificate Pricing (NCP) that exploits this asymmetry under an unsupervised learning framework. A neural network is trained to predict certificate-level dual prices, while a structured recovery layer constructs the induced primal marginal. NCP can be viewed as amortized separation: instead of enumerating violated inequalities, it learns the residual prices through which their aggregate effect enters recovery. When the certificate-consistency condition holds, the recovered marginal is globally feasible, and a local theory shows that first-order errors in the predicted price induce only second-order loss in objective value. Across three classes of CO problems, NCP either outperforms state-of-the-art neural baselines by large margins or matches them at a fraction of the computation time, and shows stronger out-of-distribution generalization.

Jingyi Chen, Xinyuan Zhang, Xinwu Qian

Department of Civil and Environmental Engineering, Rice University, Houston, TX

Primal-Dual OptimizationUnsupervised LearningCombinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Jun 29, 2026

Optimizing Nursing Care Taxi Dispatch Leveraging Integer Linear Programming Solvers and Machine Learning

In this paper, we formulate a new vehicle dispatch optimization problem, called Nursing Care Taxi Dispatch, as a variant of the Vehicle Routing Problem, considering constraints related to wheelchair use, user compatibility, pick-up and drop-off times, and vehicle limitations. Previous neural-based methods for Vehicle Routing Problems have typically addressed a few simple constraints, while our new problem involves multiple complex constraints, resulting in having fewer destinations to select. This complexity makes it more difficult to obtain solutions that allow all nodes to be visited with a limited number of vehicles. To balance low violation rate, computational efficiency, and solution quality, we propose a supervised machine learning approach based on the Transformer architecture. We first obtain a set of high-quality solutions using an integer linear programming solver for given inputs and then train our learning model through supervised learning. Additionally, we introduce the post-processing of the paths generated by the learning model, ensuring that all constraints are satisfied. We compared each instance's objective function value (operating time), execution time, and constraint violation rate across different methods: our proposed method and some existing methods including integer linear programming and machine learning-based methods, using real-world facility data. Our method successfully produced balanced solutions regarding operating time, execution time, and constraint violation rate. Notably, we observed a decrease in the operating time for all problem sizes and regions, while keeping constraint violations to a minimum compared to existing methods. Especially, the decrease reached up to 8% for problem sizes with fewer than 30 users.

Riku Nakao, Akihito Hiromori, Hamada Rizk +1

The University of Osaka, Japan · RIKEN R-CCS, Japan · Tanta University, Egypt

Vehicle RoutingNeural Combinatorial Optimization
AskPDF
Jun 22, 2026

GeoRouteNet: Geometry-Enhanced Non-Autoregressive Neural Solver for the Traveling Salesman Problem

The traveling salesman problem (TSP) is a canonical NP-hard combinatorial optimization benchmark that tests the representational capacity and generalization of neural solvers. While non-autoregressive (NAR) approaches offer parallel inference, they often lack sufficient geometric inductive bias and stable training signals, leading to degraded performance under cross-scale and cross-distribution shifts. We propose GeoRouteNet, a geometry-enhanced NAR neural solver for Euclidean TSP. On the model side, GeoRouteNet incorporates centered node features, learnable radial distance basis functions, distance-aware graph attention with explicit edge messaging, LayerNorm-SwiGLU feed-forward blocks, and cross-layer attentive residual mixing. On the training side, we design multi-candidate self-comparison reinforcement learning (MCS-RL), which samples multiple candidate tours per instance, constructs adaptive baselines from greedy and peer candidates, and adds winner-candidate guidance with annealed entropy regularization. On 10,000 random TSP50 instances, GeoRouteNet achieves a 0.32% optimality gap under Beam-1000 decoding. On TSP100, the gap is 1.26%. On 27 stratified TSPLIB EUC_2D instances, the overall gap drops from 17.12% (NAR4TSP reproduction) to 3.60%, while batch inference throughput substantially exceeds that of Concorde and LKH3. Ablation studies confirm that geometric structure enhancement and multi-candidate training are complementary: structure improvements dominate cross-distribution gains, while MCS-RL further stabilizes solution quality when paired with a strong geometric encoder.

Xiang Li

College of Computer Science, Yangtze University, Jingzhou, China

Traveling Salesperson ProblemGraph Neural NetworksReinforcement LearningCombinatorial OptimizationRL for Combinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Jun 19, 2026

Learning to Place Guards by Reinforcement: A Geo-Free Neural Policy for the Vertex-Guard Art Gallery Problem

Neural combinatorial optimization (NCO) has shown that policies trained by reinforcement can construct strong solutions to NP-hard problems directly from raw instances. What such a policy actually learns, as opposed to what its decoder expresses, remains much less clear. We study this distinction on the vertex-guard Art Gallery Problem, the NP-hard task of choosing polygon vertices from which to observe an entire region. A pointer-network policy is trained from a coverage-aware reward over its own rollouts under the constraint we call geo-free inference: at test time it sees only vertex coordinates, with no visibility computation and no geometric oracle. The policy places guards economically but leaves a tail of under-covered polygons that widens far beyond the training range. To locate the cause, we freeze the trained encoder and read its embeddings with a small single-shot classifier, still geo-free at inference. The classifier closes most of the feasibility gap, in and out of distribution and at up to roughly five times the training range, cutting under-covered polygons by about an order of magnitude at an explicitly reported cost in guard count. We read this as evidence that the reinforcement-trained representation already encodes the geometry required for feasibility, and that residual failures reflect decoder calibration rather than missing knowledge. Probing a frozen encoder thus offers a practical way to ask what a neural combinatorial solver has internalized.

Domagoj Ševerdija, Jurica Maltar, Nathan Chappel +1

School of Applied Mathematics and Informatics, University J. J. Strossmayer of Osijek, Croatia

Representation ProbingRL for Combinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Jun 18, 2026

Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks

Neural Combinatorial Optimization (NCO) achieves strong performance, yet its black-box nature remains a key roadblock to deployment and scientific diagnosis. Standard interpretability tools, such as Concept Bottleneck Models (CBMs), are ill-equipped for NCO, whose decisions are dynamic, state-dependent, and lack proper concept vocabulary definition. To close this gap, we introduce Evolving Programmatic Bottlenecks (EPB), to our knowledge, the first framework for interpreting NCO policies by distilling black-box NCO models into human-readable program portfolios. EPB employs an LLM to autonomously evolve a bank of programs, where each program's per-step action distribution serves as the bottleneck. EPB works through an iterative framework: Block I fixes program bank capacity and introduces a hybrid textual-numerical gradient descent scheme that couples numerical gradients for student router updates and textual gradients for LLM-based program revision; Block II dynamically adapts bank capacity via fault-targeted expansion and redundancy pruning. Extensive experiments demonstrate EPB's effectiveness and broad applicability, where the distilled program portfolios largely match original performance. EPB also reveals that NCO behavior shifts across optimization stages and can be approximated as a composition of classic heuristic variants. Our work advances interpretable NCO and establishes EPB as a promising tool for interpreting sequential decision-making models.

Haocheng Duan, Yuxin Guo, Jieyi Bi +4

1Carnegie Mellon University · 2Nanyang Technological University · 3Microsoft Research +1

Neural Network InterpretabilityNeural Combinatorial Optimization
AskPDF
Jun 17, 2026

AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network

The Traveling Salesman Problem (TSP) is a cornerstone of combinatorial optimization and arises in many practical scenarios. Although graph-based learning approaches have been explored for TSP, the question of how to exploit graph structure more effectively remains open. We present the Anisotropic Graph Diffusion Network (AGDN), a new Graph Neural Network framework designed to solve TSP. Our method tackles two central difficulties: (1) the lack of informative topological prior in fully connected TSP graphs, and (2) losing connected nodes in the optimal solution after the commonly used graph sparsification techniques. To overcome these issues, we construct a MixScore transition matrix that merges node similarity with pairwise distance, and we develop an anisotropic graph diffusion strategy that supports efficient information exchange across multiple hops. Comprehensive experiments spanning diverse instance sizes and node distributions show that AGDN consistently outperforms existing methods while keeping computation time competitive. Furthermore, AGDN generalizes well to problem sizes and distributions beyond those seen during training. The implementation is publicly available at: https://github.com/LabRAI/AGDN.

Bolin Shen, Ziwei Huang, Zhiguang Cao +1

Florida State University · Tallahassee, United States · Singapore Management University +1

Traveling Salesperson ProblemGraph Neural NetworksCombinatorial OptimizationNeural Combinatorial OptimizationGraph Diffusion
AskPDF
Jun 16, 2026

N(CO)2^2: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering

Neural combinatorial optimization (NCO) offers a promising alternative to traditional heuristic-based methods for solving complex graph optimization problems by proposing to learn heuristics through data. This class of problems frequently arises in automation, as it can be used to model a variety of applications. While NCO has been extensively studied for deterministic combinatorial optimization problems, there are only a few works that aim to solve stochastic combinatorial optimization problems. In this work, we present N(CO)2^2: Neural Combinatorial Optimization with Chance cOnstraints to solve the Stochastic Orienteering Problem (SOP) without the use of hand-crafted heuristics. By integrating a reinforcement learning (RL) framework, the model optimizes path selection under uncertainty, effectively balancing exploration and exploitation. Empirical results demonstrate that our method generalizes well across diverse SOP instances, achieving competitive performance compared to the state-of-the-art mixed-integer linear program (MILP) for the task. The proposed approach reduces human effort in heuristic design while enabling adaptive and efficient decision-making in uncertain environments.

Anas Saeed, Marcos Abel Zuzuárregui, Stefano Carpin

Department of Computer Science and Engineering, University of California, Merced, CA, USA

Stochastic OptimizationChance-Constrained OptimizationCombinatorial OptimizationRL for Combinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Jun 16, 2026

Deep Reinforcement Learning for Minimum Zero-Forcing Sets

This paper explores the problem of finding the minimum zero-forcing set on undirected graphs and proposes an adapted machine-learning framework to solve the problem. The minimum zero-forcing set problem is a graph coloring problem where the color of an initial set of nodes propagates throughout a network. The set of nodes is zero-forcing if it forces all uncolored nodes to change color under the constraint of the color-change rule. There are several applications to this problem across different domains such as network science, network control, and designing logical circuits. Finding the minimum zero-forcing set is shown to be NP-hard. We propose a reinforcement learning framework, SD-ZFS, that adapts the S2V-DQN architecture to the ZFS problem. We train several models on this adapted framework and analyze the performance across graph datasets that have varying structures. We evaluate how the models trained on the framework generalize, scale, and transfer to different network types. The results demonstrate the effectiveness of the framework when compared against the optimal solution and greedy heuristic. We provide further insight into how the ZFS problem can be solved through machine-learning and the influence of network structure on the problem.

Steve Halley, Maurício Gruppi

Department of Computing Sciences, Villanova University Villanova, Pennsylvania, USA

Reinforcement LearningCombinatorial OptimizationRL for Combinatorial OptimizationNeural Combinatorial Optimization
AskPDF