Research map / Graph learning / Graph algorithms and clustering
GOAL: A Generalist Combinatorial Optimization Agent Learner
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GOAL, a single transformer backbone with light task-specific adapters and mixed-attention/multi-type blocks, trained by imitation on eight CO problems and fine-tuned to new ones.
Problem
Neural combinatorial optimization models are specialized per problem and must be retrained from scratch for each variant; there is little cross-problem generalization for CO.
Approach
A shared backbone (BQ-NCO based) with low-rank task-specific input adapters projected through a shared codebook, mixed-attention blocks that inject edge features into attention scores, and a multi-type transformer that duplicates shared-parameter attention blocks per node/edge type pair; trained by imitation of solver solutions and fine-tuned to new tasks with supervised or unsupervised (Apprentic
Key results
- Single-task GOAL achieves best gap on 7 of 8 training tasks (e.g., ATSP100 0.30% vs BQ-NCO 1.27%, CVRPTW100 2.61%), while multi-task GOAL is only slightly worse (e.g., ATSP100 0.91%).
- Unsupervised fine-tuning of the multi-task GOAL to eight unseen COPs outperforms training from scratch at comparable time budgets, and supervised fine-tuning takes only a few minutes with 128 labeled instances.
- Mixed-attention and multi-type architecture ablations: on JSSP the multi-type model reaches 4.6% test gap vs 8.9% for single-type after 200 epochs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use multi-type architecture instead of single-type architecture (ablation) | GOAL on JSSP · JSSP | test optimality gap: 8.9% -> 4.6% | Helped |
| replace GOAL mixed-attention blocks with MatNet attention (ablation) | GOAL on ATSP · ATSP | optimality gap | Hurt |
| replace GOAL mixed-attention blocks with G2G attention (ablation) | GOAL on ATSP · ATSP | optimality gap | Hurt |
| add a shared codebook to sparsify the input adapter (ablation) | GOAL during supervised fine-tuning · PCTSP | optimality gap | Helped |
| train GOAL as a multi-task model instead of a single-task model | GOAL · training tasks (ATSP, CVRP, CVRPTW, OP, KP, MVC, UMSP, JSSP) | gap: 0.30% -> 0.91%; 2.34% -> 3.16%; 2.61% -> 3.82%; -0.04% -> 0.43%; 0.10% -> 0.12%; 0.23% -> 0.37%; 2.82% -> 3.84%; 2.73% - | Hurt |
Surprising findings
- Multi-task GOAL is not substantially worse than single-task models despite sharing a single backbone across eight problems with heterogeneous structures.
- Generalization to 10x larger instances is weaker than some baselines on CVRP (GOAL 7.37% vs BQ-NCO 5.88% at 1000 nodes).
Limitations
- Requires good-quality solutions from specialized solvers for imitation pretraining, though unsupervised fine-tuning is possible.
- Quadratic complexity of attention makes the approach costly beyond about a thousand nodes.
- Limited to problems where feasibility is easy to ensure during constructive decoding and representable as graphs with iterative node selection.
Experimental setup
Datasets: randomly generated instances for ATSP, CVRP, CVRPTW, OP, KP, MVC, UMSP, JSSP solved by LKH, HGS, A4OP, ORTools, FastWVC,
Benchmarks: ATSP100 CVRP100 CVRPTW100 OP100 KP100 MVC100 UMSP100x20 JSSP10x10 eight unseen tasks (TRP, PCTSP, OCVRP, SDCVRP, SOP, MCLP, MIS, OSSP)
Metrics: optimality gap time
Baselines: AM MDAM POMO Sym-NCO BQ-NCO MVMoE MatNet S2V-DQN RouteFinder COMPASS Gumbeldore
Builds on: BQ-NCO Attention Model ExIt adapters
Closest papers by meaning
- Curriculum learning for multilevel budgeted combinatorial problems (NeurIPS 2020 · similarity 0.89)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.88)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.88)
- CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization (AAAI 2026 · similarity 0.88)
- Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph (ICML 2024 · similarity 0.88)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.