On the Generalization of Neural Combinatorial Optimization Heuristics
This addresses the generalization issue in neural combinatorial optimization for researchers and practitioners, but it is incremental as it builds on existing meta-learning techniques.
The paper tackles the generalization problem in neural combinatorial optimization heuristics, where models trained on certain instance types underperform on others, by proposing a meta-learning approach that treats solving over different instance distributions as separate tasks. The result shows significant improvement in generalization for two state-of-the-art models across synthetic and realistic instances.
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.