Neural Combinatorial Optimization

Follow this topic Ask about this topic

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

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

Reward-Weighted Preference Optimization for Selective Combinatorial Optimization Problems
Oct 22, 2026Haohui Zhang, Xinyu Hu, Wouter van Heeswijk +2RL for Combinatorial Optimization Combinatorial Optimization
University of Twente, Enschede, Netherlands · University of Bath, Bath, United Kingdom · Delft University of Technology, Delft, Netherlands
TRCM: Topology-Aware Route-Consistency Modeling for Robust Neural Vehicle Routing
Oct 20, 2026Peiheng Jian, Zhenwei Wang, Tiehua Zhang +4Vehicle Routing Neural Combinatorial Optimization
School of Computer Science and Technology, Tongji University, Shanghai, 201804, China · School of Computer Science, University of Nottingham Ningbo China, Ningbo, 315100, China · Yixin Group Limited, Beijing, China +1
PACT: Plan-Augmented Coordination via Trace-Graphs for Dynamic Multi-Agent Combinatorial Optimization
Oct 19, 2026Xiao Zhou, Alex Schutz, Victor-Alexandru Darvariu +1Multi-Agent System Optimization Multi-Agent Coordination
Oxford Robotics Institute University of Oxford OX1 3PJ, Oxford, United Kingdom.
CoRS: Fast Neural Flexible Job-Shop Scheduling via Composite Interval State Reuse
Oct 19, 2026Jiang Sutong, Zhao Peng, Wu Xuan +6Flexible Job Shop Scheduling Neural Combinatorial Optimization
College of Computer Science and Technology, Jilin University, China · College of Software, Jilin University, China · College of Computing and Data Science, Nanyang Technological University, Singapore +1
LangNCO: Compiling Natural-Language Constraints into Inference-Time Interventions for Neural Combinatorial Optimization
Oct 16, 2026Hironori OhigashiNeural Combinatorial Optimization Natural Language to Optimization Modeling
Panasonic Connect Co., Ltd.
RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem
Oct 10, 2026Vladimir Kirill Bickov, Neil Yorke-SmithNeural Combinatorial Optimization Vehicle Routing
Delft University of Technology, The Netherlands
GREAT-ESDD: Graph Edge Attention Network for Effectively Steered Delivery Decisions
Oct 10, 2026Attila Lischka, Ze Zhou, Xuegang +2Operations Research Vehicle Routing
Jeff · Civil and Environmental Engineering, University of Washington, Seattle, USA · Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden
EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization
Oct 4, 2026Ruogu Chen, Jie HanCombinatorial Optimization Neural Combinatorial Optimization
Department of Electrical and Computer Engineering, University of Alberta, Edmonton, AB, Canada T6G 1H9
RAOA: Alternating-Operator Neural Computation with Programmable Radio Propagation
Oct 2, 2026Toshiaki Koike-AkinoOnline Language Model Adaptation Recurrent Neural Networks
Mitsubishi Electric Research Laboratories (MERL), 201 Broadway, Cambridge, MA 02139, USA
Autoregressive Differentiable Method for Integer Programming
Oct 1, 2026Ouns El Harzli, Yudong CaoCombinatorial Optimization Neural Combinatorial Optimization
BCG X AI Science Institute Boston, USA · Zapata Quantum Boston, USA
MiLoop: Selective Memory Propagation for Neural Combinatorial Optimization
Oct 1, 2026Changliang Zhou, Yuanyao Chen, Rongsheng Chen +2Memory-Augmented Neural Networks RL for Combinatorial Optimization
School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China · Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, Southern University of Science and Technology, Shenzhen, China · Pengcheng Laboratory, Shenzhen, China
Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon
Sep 30, 2026Johannes F. Loevenich, Thies Moehlenhof, Laurin Holz +3Graph Neural Networks Approximation Algorithms
cortAIx Labs, Thales Deutschland, Ditzingen, Germany · Department of Mathematics/Computer Science, University of Osnabrück, Osnabrück, Germany
Parallel Tempering for Diffusion-Based Combinatorial Optimization
Sep 29, 2026Arman Mielke, Uwe Bauknecht, Thilo Strauss +1Combinatorial Optimization Neural Combinatorial Optimization
ETAS Research · University of Stuttgart · Max Planck Research School for Intelligent Systems (IMPRS-IS) +2
VLM Fine-Tuning for End-to-End Combinatorial Optimization
Sep 29, 2026Qingsong Yan, Xia Jiang, Yaoxin Wu +3LLM Fine-Tuning Neural Combinatorial Optimization
College of Computer Science, Sichuan University · Department of Industrial Engineering&Innovation Sciences, Eindhoven University of Technology · Institute of Marine Science and Technology, Shandong University +1
Understanding Decision-Making Mechanisms in Neural Routing Solvers
Sep 28, 2026Fatemeh Askari, Mazdak Teymourian, Mohammad Izadi +1Mechanistic Interpretability Neural Network Interpretability
Department of Computer EngineeringSharif University of Technology
Depot-Closed Multi-Component Construction for Neural Vehicle Routing
Sep 28, 2026Shinichiro Hamada, Hisashi KashimaVehicle Routing Neural Combinatorial Optimization
Core Technology, R&D Division Panasonic Connect Co., Ltd. · Graduate School of Informatics Kyoto University
Compute Time Scaling with Recursive Models for Combinatorial Optimization
Sep 28, 2026Zhengxi Zhang, Paul SwobodaTraveling Salesperson Problem Inference-Time Scaling
Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe
Sep 22, 2026Akbar Rafiey, Yifei Xu, Nikolaos KaraliasSelf-Supervised Learning Combinatorial Optimization
NYU · MIT
Deep Reinforcement Learning on Item-Compatibility Graphs for One-Dimensional Bin Packing
Sep 21, 2026M. Aslı AydınCombinatorial Optimization RL for Combinatorial Optimization
Department of Management Engineering, Bahçeşehir University, Istanbul, Türkiye
COMPASS: Ordered Clustered Routing at 100K Scale
Sep 17, 2026Ido Greenberg, Hugo Linsenmaier, Piotr Sielski +4Traveling Salesperson Problem Combinatorial Optimization
NVIDIA
Graph Neural Networks for Influence Maximization in Social Networks: An Unsupervised Minimum Dominating Set Approach
Sep 12, 2026Erfan Ahmadi, Mina Shirazi, Behnam BahrakSocial Network Analysis Influence Maximization
Computer Engineering Department, Tehran Institute for Advanced Studies (TeIAS), Tehran, Iran. · University of Tehran, Tehran, Iran.
HyCO: A Hybrid Neural Solver for Combinatorial Optimization
Sep 7, 2026Yuheng Li, Di Yang, Haipeng Chen +1RL for Combinatorial Optimization Neural Combinatorial Optimization
Department of Data Science College of William & Mary
Graph neural networks and the energetic cavity method for combinatorial optimization
Sep 7, 2026Joe Bacchus George, George T. CantwellGraph Neural Networks Combinatorial Optimization
Department of Engineering, University of Cambridge, CB2 1PZ, United Kingdom
GeoPAR: Large-Scale Multi-Agent Combinatorial Optimization with Geometry-Guided Parallel Autoregressive Learning
Sep 1, 2026Wenjian Wu, Zesheng Jia, Jiaying Tang +2Combinatorial Optimization Vehicle Routing
School of Future Science and Engineering, Soochow University, Suzhou, China
A hybrid quantum-classical neural network for learning to route
Aug 31, 2026Marcus Rolf Peter Ritt, Alexsandro Santos da Rosa Júnior, Marcos Vinicius Reballo +2Hybrid Quantum-Classical ML Vehicle Routing
Instituto de Pesquisas Eldorado – Porto Alegre – RS – Brazil · Departamento de Física, Universidade Federal de Santa Catarina, Florianópolis 88040-900, SC, Brazil
Transformer-Based Flow Shop Scheduling Using MILP-Generated Training Data
Aug 30, 2026Roderich WallrathTransformer Combinatorial Optimization
University of Twente, Faculty of Science and Technology, Sustainable Process Technology, Process Design and Optimization, Drienerlolaan 5, 7522 NB Enschede, The Netherlands
SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming
Aug 26, 2026Zherong Zhang, Guanlin Li, Chengrui Gao +5Mixed-Integer Linear Programming Neural Combinatorial Optimization
State Key Laboratory of Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University · State Key Laboratory of Technology and Equipment for Defense Against Power System Operational Risks, Nari Technology Co., Ltd.
Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement
Aug 25, 2026Arthur Corrêa, Paulo Nascimento, Samuel MonizVehicle Routing Neural Combinatorial Optimization
University of Coimbra, CEMMPRE, ARISE Department of Mechanical Engineering, Coimbra 3030-788, Portugal
Spread and Scale: What Determines Whether Test-Time Budget Allocation Pays
Aug 21, 2026Jinhyung BaeInference-Time Compute Allocation Neural Combinatorial Optimization
Department of Industrial and Management Engineering / AI Data Convergence, Hankuk University of Foreign Studies, Yongin, Republic of Korea.
Congruence Decomposition with Neural Block Solvers for Large-Scale PCI Assignment
Aug 21, 2026Yeqing Qiu, Chengpiao Huang, Ye Xue +7Combinatorial Optimization Wireless Resource Allocation
School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen, China, and Shenzhen Research Institute of Big Data, Shenzhen, China · Shenzhen Research Institute of Big Data, Shenzhen, China · Department of Industrial Engineering and Operations Research, Columbia University, New York, USA +5

Oct 22, 2026J/K move · Enter open · S save

Reward-Weighted Preference Optimization for Selective Combinatorial Optimization Problems

Haohui Zhang, Xinyu Hu, Wouter van Heeswijk, Neil Yorke-Smith+1

University of Twente, Enschede, Netherlands · University of Bath, Bath, United Kingdom · Delft University of Technology, Delft, Netherlands

RL for Combinatorial Optimization Combinatorial Optimization Neural Combinatorial Optimization Preference-Based RL Pairwise Preference Learning

Open paper AskPDF arXiv

Reinforcement learning has emerged as an effective approach for combinatorial optimization, but most existing methods focus on problems such as the Travelling Salesperson Problem (TSP) in which all elements must be served. Selective combinatorial optimization problems (SCOPs), including the Orienteering Problem (OP), Prize-Collecting TSP (PCTSP), Stochastic PCTSP and Knapsack Problem (KP), additionally require selecting which elements to include. This selection creates sampled solutions with substantially different objective values, yet standard preference optimization reduces such comparisons to binary rankings and discards the magnitude of these differences. We introduce Reward-Weighted Preference Optimization (RWPO), a pairwise training objective that incorporates reward-gap information into preference learning. For candidate trajectories sampled from the same instance, RWPO weights each preference loss according to the normalized difference in their rewards, assigning greater training emphasis to comparisons that represent larger improvements in solution quality. We further combine RWPO with scale-specific fine-tuning and reward- and likelihood-weighted tilted sampling to adapt trained policies to larger and shifted instance distributions without relying on local-search post-processing. Experiments on the OP, PCTSP, Stochastic PCTSP, and KP show that RWPO consistently improves over unweighted preference optimization and policy-gradient baselines across a wide range of instance sizes. On the OP, the resulting solver exceeds the mean reward of the Compass metaheuristic at scales from 100 to 2,000 nodes. The results demonstrate that preserving reward-gap information can substantially improve preference-based learning for selective combinatorial optimization and support generalization to large-scale instances.