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.

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

    Aug 14, 2026Andrew Soroka, Alex MeshcheryakovVehicle RoutingNeural Combinatorial Optimization

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

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

    Aug 14, 2026Andrew Soroka, German Mikhelson, Alexander Mescheryakov +1Vehicle RoutingMetaheuristic Optimization

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

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

    Aug 13, 2026Jinhyung BaeAlgorithmic AuditingInference-Time Compute Allocation

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

  4. Constrained Graph Diffusion for Mixed Integer Optimization

    Aug 13, 2026Vincenzo Di Vito, Yusuf Guven, Babak Badnava +3Mixed-Integer Linear ProgrammingConstrained Optimization

    University of Virginia · MIT · Los Alamos National Laboratory

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

    Aug 12, 2026Yuanyu Li, Jintao Xu, Zijiang Liu +6Combinatorial OptimizationPreference Optimization

    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

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

    Aug 10, 2026Yancheng Song, Yongzhi Qi, Wei Qi +1Traveling Salesperson ProblemPrimal-Dual Optimization

    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

  7. Neuro-Evolved Heuristics for Variable Gapped Common Subsequence Identification

    Aug 1, 2026Marko Djukanović, Christian Blum, Aleksandar Kartelj +2Automated Heuristic DesignNeural Combinatorial Optimization

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

  8. Stabilized Best-of-KK Training for Neural Combinatorial Optimization

    Jul 31, 2026Melveena Jolly, Midhun XavierTraveling Salesperson ProblemBest-of-N Sampling

    1Independent Researcher

  9. Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization

    Jul 31, 2026David Aguado, Daniel Fuertes, Carlos R. del-Blanco +1Traveling Salesperson ProblemSelf-Supervised Learning

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

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

    Jul 30, 2026Mohand Mezmaz, Grégoire DanoyMetaheuristic OptimizationCombinatorial Optimization

    SnT, University of Luxembourg

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

    Jul 30, 2026Shengda Gu, Kai Li, Xinyi Ke +3Automated Algorithm DiscoveryPairwise Preference Evaluation

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

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

    Jul 26, 2026Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang +1Traveling Salesperson ProblemInference-Time Search

    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

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

    Jul 26, 2026Haomiao Sun, Fang He, Congyuan Ji +1Graph Attention NetworksLearning to Optimize

    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

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

    Jul 24, 2026Yida Xu, Zhaofang Mao, Yuheng Miao +2Vehicle RoutingSupply Chain Management

    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

  15. On the Effectiveness of Pretraining for Graph Combinatorial Optimization

    Jul 21, 2026David Aguado, Daniel Fuertes, Carlos R. del-Blanco +1Traveling Salesperson ProblemSelf-Supervised Pre-Training

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

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

    Jul 21, 2026Leyre Encío, Daniel Fuertes, Carlos R. del-Blanco +1Relative Positional EncodingCombinatorial Optimization

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

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

    Jul 20, 2026Yang Wang, Ya-Hui Jia, Wei-Neng Chen +3Large Language Model-Guided OptimizationMulti-Task Learning

    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

  18. Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

    Jul 17, 2026Filip Sabo, Aida Todri-SanialSudoku SolvingOscillatory Neural Networks

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

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

    Jul 13, 2026Ke Sun, Xinyuan Zhang, Xinwu QianTraveling Salesperson ProblemCombinatorial Optimization

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

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

    Jul 5, 2026Sohaib AfifiGradient-Based AttributionCounterfactual Explanations

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

  21. TSP with Predictions: Heatmap to Tour with Provable Guarantees

    Jul 4, 2026Marek Eliáš, Fabrizio Grandoni, Adam Polak +1Traveling Salesperson ProblemCombinatorial Optimization

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

    Jul 3, 2026Driss Chraibi, Alejandro García Pis, Stéphane Grihon +1Materials ScienceNeural Combinatorial Optimization

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

  23. Neural Certificate Pricing for Combinatorial Optimization Problems

    Jul 1, 2026Jingyi Chen, Xinyuan Zhang, Xinwu QianPrimal-Dual OptimizationUnsupervised Learning

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

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

    Jun 29, 2026Riku Nakao, Akihito Hiromori, Hamada Rizk +1Vehicle RoutingNeural Combinatorial Optimization

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

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

    Jun 22, 2026Xiang LiTraveling Salesperson ProblemGraph Neural Networks

    College of Computer Science, Yangtze University, Jingzhou, China

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

    Jun 19, 2026Domagoj Ševerdija, Jurica Maltar, Nathan Chappel +1Representation ProbingRL for Combinatorial Optimization

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

  27. Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks

    Jun 18, 2026Haocheng Duan, Yuxin Guo, Jieyi Bi +4Neural Network InterpretabilityNeural Combinatorial Optimization

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

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

    Jun 17, 2026Bolin Shen, Ziwei Huang, Zhiguang Cao +1Traveling Salesperson ProblemGraph Neural Networks

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

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

    Jun 16, 2026Anas Saeed, Marcos Abel Zuzuárregui, Stefano CarpinStochastic OptimizationChance-Constrained Optimization

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

  30. Deep Reinforcement Learning for Minimum Zero-Forcing Sets

    Jun 16, 2026Steve Halley, Maurício GruppiReinforcement LearningCombinatorial Optimization

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