Zero Training Overhead Portfolios for Learning to Solve Combinatorial
  Problems
  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.
