mlsanityData to 7 Oct 2026

Matrix Encoding Networks for Neural Combinatorial Optimization

arXiv 2106.11113 ↗First posted 21 Jun 2021cs.LGcited by 89

Not on the map. Why?

Abstract (arXiv)

Machine Learning (ML) can help solve combinatorial optimization (CO) problems better. A popular approach is to use a neural net to compute on the parameters of a given CO problem and extract useful information that guides the search for good solutions. Many CO problems of practical importance can be specified in a matrix form of parameters quantifying the relationship between two groups of items. There is currently no neural net model, however, that takes in such matrix-style relationship data as an input. Consequently, these types of CO problems have been out of reach for ML engineers. In this paper, we introduce Matrix Encoding Network (MatNet) and show how conveniently it takes in and processes parameters of such complex CO problems. Using an end-to-end model based on MatNet, we solve asymmetric traveling salesman (ATSP) and flexible flow shop (FFSP) problems as the earliest neural approach. In particular, for a class of FFSP we have tested MatNet on, we demonstrate a far superior empirical performance to any methods (neural or not) known to date.

Key facts. Cited by 89 papers in the map (data through 7 Oct 2026). Builds on 23 of its 42 references that are in the map. First posted on arXiv 21 Jun 2021.

Builds on

23 of 42 references.

References · 23

  1. 2017Attention Is All You Needcited by 59,932
  2. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  4. 2017Graph Attention Networkscited by 8,854
  5. 2014Sequence to Sequence Learning with Neural Networkscited by 2,974
  6. 2015Pointer Networkscited by 882
  7. 2020A Generalization of Transformer Networks to Graphscited by 653
  8. 2018Attention, Learn to Solve Routing Problems!cited by 646
  9. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  10. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  11. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  12. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
11 more
  1. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  2. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  3. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  4. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  5. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  6. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 162
  7. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  8. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  9. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  10. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
  11. 2020Multi-Agent Routing Value Iteration Networkcited by 17

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 8; 2023: 14; 2024: 25; 2025: 24; 2026: 17.

89 papers.

Sort:

By area:

  1. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 258
  2. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  3. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 140
  4. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  5. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  6. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 82
  7. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  8. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  9. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  10. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 61
  11. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 54
  12. 2023Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problemcited by 49
38 more
  1. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 39
  2. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 36
  3. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  4. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  5. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  6. 2025Large Language Models as End-to-end Combinatorial Optimization Solverscited by 27
  7. 2024Cross-Problem Learning for Solving Vehicle Routing Problemscited by 24
  8. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  9. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  10. 2023Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimizationcited by 21
  11. 2022Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Schedulingcited by 20
  12. 2023Flexible Job Shop Scheduling via Dual Attention Network Based Reinforcement Learningcited by 20
  13. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 19
  14. 2024DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problemscited by 18
  15. 2024LinSATNet: The Positive Linear Satisfiability Neural Networkscited by 16
  16. 2024Graph Neural Networks for Job Shop Scheduling Problems: A Surveycited by 15
  17. 2023Neural Multi-Objective Combinatorial Optimization with Diversity Enhancementcited by 13
  18. 2025Planning of Heuristics: Strategic Planning on Large Language Models with Monte Carlo Tree Search for Automating Heuristic Optimizationcited by 13
  19. 2025MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solvercited by 13
  20. 2025Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learningcited by 12
  21. 2025Preference Optimization for Combinatorial Optimization Problemscited by 11
  22. 2025Adversarial Generative Flow Network for Solving Vehicle Routing Problemscited by 10
  23. 2025RRNCO: Towards Real-World Routing with Neural Combinatorial Optimizationcited by 10
  24. 2022Unsupervised Training for Neural TSP Solvercited by 9
  25. 2024Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solvercited by 9
  26. 2024Collaboration! Towards Robust Neural Methods for Routing Problemscited by 9
  27. 2024A GREAT Architecture for Edge-Based Graph Problems Like TSPcited by 7
  28. 2024PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimizationcited by 7
  29. 2025URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalizationcited by 7
  30. 2025Hybrid-Balance GFlowNet for Solving Vehicle Routing Problemscited by 7
  31. 2026RADAR: Learning to Route with Asymmetry-aware DistAnce Representationscited by 7
  32. 2023Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimizationcited by 6
  33. 2025Learning for routing: A guided review of recent developments and future directionscited by 6
  34. 2023Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscited by 5
  35. 2024Learning Topological Representations with Bidirectional Graph Attention Network for Solving Job Shop Scheduling Problemcited by 5
  36. 2024Leader Reward for POMO-Based Neural Combinatorial Optimizationcited by 5
  37. 2024Neural Solver Selection for Combinatorial Optimizationcited by 5
  38. 2025EFormer: An Effective Edge-based Transformer for Vehicle Routing Problemscited by 5

50 most cited of 89 All 89 (JSON)