# Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 66 references that are in the map.
- First posted on arXiv 5 Feb 2021.

## Builds on (most cited first, 24 of 24)

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Deep Networks with Stochastic Depth](https://mlsanity.com/paper/1603.09382/) (2016)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Snapshot Ensembles: Train 1, get M for free](https://mlsanity.com/paper/1704.00109/) (2017)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [CNN-RNN: A Unified Framework for Multi-label Image Classification](https://mlsanity.com/paper/1604.04573/) (2016)
- [Knowledge Distillation by On-the-Fly Native Ensemble](https://mlsanity.com/paper/1806.04606/) (2018)
- [Discriminative Embeddings of Latent Variable Models for Structured Data](https://mlsanity.com/paper/1603.05629/) (2016)
- [A Closer Look at Deep Learning Heuristics: Learning rate restarts, Warmup and Distillation](https://mlsanity.com/paper/1810.13243/) (2018)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Zoneout: Regularizing RNNs by Randomly Preserving Hidden Activations](https://mlsanity.com/paper/1606.01305/) (2016)
- [MEAL: Multi-Model Ensemble via Adversarial Learning](https://mlsanity.com/paper/1812.02425/) (2018)
- [Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero](https://mlsanity.com/paper/1905.11623/) (2019)
- [Neural Message Passing for Multi-Label Classification](https://mlsanity.com/paper/1904.08049/) (2019)
- [Swapout: Learning an ensemble of deep architectures](https://mlsanity.com/paper/1605.06465/) (2016)
- [Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?](https://mlsanity.com/paper/1909.11830/) (2019)
- [Co-training for Policy Learning](https://mlsanity.com/paper/1907.04484/) (2019)

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

- [Neural Solver Selection for Combinatorial Optimization](https://mlsanity.com/paper/2410.09693/) (2024)

## Abstract (arXiv)

There has been an increasing interest in harnessing deep learning to tackle combinatorial optimization (CO) problems in recent years. Typical CO deep learning approaches leverage the problem structure in the model architecture. Nevertheless, the model selection is still mainly based on the conventional machine learning setting. Due to the discrete nature of CO problems, a single model is unlikely to learn the problem entirely. We introduce ZTop, which stands for Zero Training Overhead Portfolio, a simple yet effective model selection and ensemble mechanism for learning to solve combinatorial problems. ZTop is inspired by algorithm portfolios, a popular CO ensembling strategy, particularly restart portfolios, which periodically restart a randomized CO algorithm, de facto exploring the search space with different heuristics. We have observed that well-trained models acquired in the same training trajectory, with similar top validation performance, perform well on very different validation instances. Following this observation, ZTop ensembles a set of well-trained models, each providing a unique heuristic with zero training overhead, and applies them, sequentially or in parallel, to solve the test instances. We show how ZTopping, i.e., using a ZTop ensemble strategy with a given deep learning approach, can significantly improve the performance of the current state-of-the-art deep learning approaches on three prototypical CO domains, the hardest unique-solution Sudoku instances, challenging routing problems, and the graph maximum cut problem, as well as on multi-label classification, a machine learning task with a large combinatorial label space.