# Moco: A Learnable Meta Optimizer for Combinatorial Optimization

arXiv: https://arxiv.org/abs/2402.04915 · HTML: https://mlsanity.com/paper/2402.04915/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 53 references that are in the map.
- First posted on arXiv 7 Feb 2024.

## Builds on (most cited first, 30 of 40)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Learning to Delegate for Large-scale Vehicle Routing](https://mlsanity.com/paper/2107.04139/) (2021)
- [Efficient Active Search for Combinatorial Optimization Problems](https://mlsanity.com/paper/2106.05126/) (2021)
- [Understanding and correcting pathologies in the training of learned optimizers](https://mlsanity.com/paper/1810.10180/) (2018)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [Tasks, stability, architecture, and compute: Training more effective learned optimizers, and using them to train themselves](https://mlsanity.com/paper/2009.11243/) (2020)
- [Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization](https://mlsanity.com/paper/2210.03475/) (2022)
- [Unsupervised Learning for Solving the Travelling Salesman Problem](https://mlsanity.com/paper/2303.10538/) (2023)
- [VeLO: Training Versatile Learned Optimizers by Scaling Up](https://mlsanity.com/paper/2211.09760/) (2022)
- [Learning What to Defer for Maximum Independent Sets](https://mlsanity.com/paper/2006.09607/) (2020)

## Built on by (most cited first, 5 of 5)

- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Memory-Enhanced Neural Solvers for Routing Problems](https://mlsanity.com/paper/2406.16424/) (2024)
- [CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization](https://mlsanity.com/paper/2602.08210/) (2026)
- [A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems](https://mlsanity.com/paper/2605.14416/) (2026)
- [Compute Time Scaling with Recursive Models for Combinatorial Optimization](https://mlsanity.com/paper/2609.34585/) (2026)

## Abstract (arXiv)

Relevant combinatorial optimization problems (COPs) are often NP-hard. While they have been tackled mainly via handcrafted heuristics in the past, advances in neural networks have motivated the development of general methods to learn heuristics from data. Many approaches utilize a neural network to directly construct a solution, but are limited in further improving based on already constructed solutions at inference time. Our approach, Moco, defines a lightweight solution construction procedure, guided by a single continuous vector θ (called heatmap) and learns a neural network to update θ for a single instance of a COP at inference time. The update is based on various features of the current search state. The training procedure is budget aware, targeting the overall best solution found during the entire search. Moco is a fully learnable meta optimizer not utilizing problem specific heuristics or requiring optimal solutions for training. We test Moco on the Traveling Salesman Problem (TSP) and Maximum Independent Set (MIS) and show that it significantly improves over other heatmap based methods.