Problem Distributions as Tasks: Repurposing Meta Learning for Generative Combinatorial Optimization towards Multi-task Pretraining and Adaptation

Despite the fast progress of Neural Combinatorial Optimization (NCO) on graphs, existing solvers mainly learn a narrow task (e.g., uniform TSP) at a time and hardly handle instances over diverse distributions. This paper proposes M$^2$GenCO, a **M**ulti-task learning framework that pioneers the instantiation of the **M**eta-learning mechanism with diffusion-based **Gen**erative solving for **CO** Problems (COPs) on graphs, first formulating "tasks" in meta-learning as distinct problem types instead of instances of the same problem. With a tailored lightweight graph neural network, our framework performs effective joint pre-training on a variety of problem types and efficient fine-tuning to adapt for out-of-distribution scenarios. Further, we establish a benchmark comprising 5 classic graph COPs with varying scales and multiple distributions, forming 38 distinct test datasets that facilitate standard evaluation of generalizability and adaptability for NCO solvers. Empirically, M$^2$GenCO with greedy decoder yields an overall 9.16\% performance gain with an average 95.6$\times$ acceleration for inference, and achieves concrete state-of-the-arts on all test sets with simple local searchers, maintaining superior solving time against previous neural methods. The computational resource and time consumption for training are saved by up to 82% and 91%, respectively.

Many real-world decisions require choosing the best option from a huge number of possibilities, such as finding efficient routes, selecting compatible items, or dividing a network into useful groups. Machine learning methods can help solve these problems, but most existing methods are trained for one specific problem type or one specific data pattern, so they often struggle when the problem changes. This paper asks whether a solver can learn more general problem-solving skills across different combinatorial optimization problems instead of starting from scratch each time. We propose M$^2$GenCO, a framework that first learns from multiple graph-based optimization problems and then quickly adapts to new problem distributions with only a small amount of additional data. We also introduce a benchmark covering five classic optimization problems across many data distributions. Experiments show that M$^2$GenCO achieves better solution quality while being much faster than many existing neural solvers. This work is a step toward more flexible optimization tools that can be reused across different planning, routing, and network decision-making tasks.