On the Generalization of Neural Combinatorial Optimization Heuristics
Neural Combinatorial Optimization approaches have recently leveraged the
expressiveness and flexibility of deep neural networks to learn efficient
heuristics for hard Combinatorial Optimization (CO) problems. However, most of
the current methods lack generalization: for a given CO problem, heuristics
which are trained on instances with certain characteristics underperform when
tested on instances with different characteristics. While some previous works
have focused on varying the training instances properties, we postulate that a
one-size-fit-all model is out of reach. Instead, we formalize solving a CO
problem over a given instance distribution as a separate learning task and
investigate meta-learning techniques to learn a model on a variety of tasks, in
order to optimize its capacity to adapt to new tasks. Through extensive
experiments, on two CO problems, using both synthetic and realistic instances,
we show that our proposed meta-learning approach significantly improves the
generalization of two state-of-the-art models.