PaperlayerView exact revision on arXiv

Source-linked AI summary

GOAL: A Generalist Combinatorial Optimization Agent Learner

Darko Drakulic, Sofia Michel, Jean-Marc Andreoli

arXiv:2406.15079v3cs.LG

TL;DR

Neural heuristics often require a separate model for each combinatorial optimization problem, and variations may require retraining. GOAL uses a shared backbone and lightweight task-specific adapters to solve diverse problems, with reported state-of-the-art single-task results on seven problems and fine-tuning to new ones.

  • Problem

    Neural heuristics commonly use separate models for individual problems, and variations can require model adjustment and retraining from scratch.

    Source: §1 · p. 2

  • Method

    GOAL combines a shared backbone with lightweight task-specific adapters, mixed-attention blocks, and a multi-type transformer to address diverse graph-structured optimization problems.

    Source: §1 · p. 2

  • Results

    GOAL solves varied combinatorial-optimization tasks with a shared backbone, achieves state-of-the-art results on seven CO problems as a single-task model, and fine-tunes to new problems.

    Source: §1 · p. 2, §5 · p. 9

  • Takeaways & Limitations

    The results demonstrate the feasibility of one backbone solving multiple optimization problems and being adapted to new tasks with or without supervision.

    Source: §5 · p. 9

    The quadratic-complexity transformer makes the approach too costly for problem sizes beyond a thousand nodes.

    Source: §5 · p. 9

Abstract

from arXiv · show

Machine Learning-based heuristics have recently shown impressive performance in solving a variety of hard combinatorial optimization problems (COPs). However, they generally rely on a separate neural model, specialized and trained for each single problem. Any variation of a problem requires adjustment of its model and re-training from scratch. In this paper, we propose GOAL (for Generalist combinatorial Optimization Agent Learner), a generalist model capable of efficiently solving multiple COPs and which can be fine-tuned to solve new COPs. GOAL consists of a single backbone plus light-weight problem-specific adapters for input and output processing. The backbone is based on a new form of mixed-attention blocks which allows to handle problems defined on graphs with arbitrary combinations of node, edge and instance-level features. Additionally, problems which involve heterogeneous types of nodes or edges are handled through a novel multi-type transformer architecture, where the attention blocks are duplicated to attend the meaningful combinations of types while relying on the same shared parameters. We train GOAL on a set of routing, scheduling and classic graph problems and show that it is only slightly inferior to the specialized baselines while being the first multi-task model that solves a wide range of COPs. Finally we showcase the strong transfer learning capacity of GOAL by fine-tuning it on several new problems. Our code is available at https://github.com/naver/goal-co/.

1. Introduction

Neural combinatorial-optimization heuristics often require separate models and retraining for problem variations, while cross-problem generalization remains less studied. GOAL uses a shared backbone with lightweight problem-specific adapters to solve and adapt across diverse optimization tasks.

1. Introduction

  • Existing neural heuristics usually specialize and train a separate model for each problem, and problem variations can require adjustment and retraining from scratch.Generalization across instance distributions has received more attention than generalization across different problems.Source: §1 · p. 2
  • GOAL combines task-specific feature projections and a shared codebook with mixed attention for edge-aware graphs and shared-parameter, type-specific attention for heterogeneous graphs.Its backbone is paired with lightweight problem-specific input and output adapters.Source: §1 · p. 2
  • The model is trained by imitation of expert trajectories across eight classic routing, scheduling, packing, and graph problems.The proposed representation targets graph problems whose feasible solutions can be constructed as sequences of node selections.Source: §1 · p. 2
  • GOAL performs very well on all training tasks, achieves state-of-the-art results on seven of eight as a single-task model, and fine-tunes to new problems in a fraction of scratch-training time and data.Fine-tuning takes minutes with few-shot imitation learning or a couple of hours without supervision.Source: §1 · p. 2
  • GOAL is presented as a single backbone that solves tasks across routing, scheduling, packing, and graph optimization and can be adapted to varied new tasks with or without supervision.The paper frames this as a step toward a foundation model for combinatorial optimization.Source: §1 · p. 3

2. Related Works

Prior neural optimization work includes constructive and improvement heuristics, with many strong models tailored to particular problem structures. Work on generalization and multitask learning provides precedents, but the cited cross-problem efforts largely focus on related routing variants or other shared task structures.

End-to-end heuristic learning for CO

  • Constructive neural heuristics have been applied to routing [21] [34] [57] [63], scheduling [37] [65], and classic problems such as knapsack [36] and maximum independent set [30,57].Improvement heuristics instead use neural networks to guide local-search operators [15] [25] [43].Source: §2 · p. 3
  • Strong neural models are often tailored to problem structure: transformer models handle Euclidean routing, while adapted distance-matrix architectures address non-Euclidean routing [37] [19].GOAL's mixed-attention modules are proposed to handle both node and edge features without overhead when either is absent.Source: §2 · p. 3

Generalization of neural heuristics

  • Recent methods improve generalization to larger instances and parameter shifts [21] [38] [54] [9] [19] [44], while cross-problem transfer has also been explored for related routing tasks [39].Other work trains on combinations of CVRP constraints to generalize to unseen combinations [7].Source: §2 · p. 3

Multi-task training for sequential decision making

  • Other multitask approaches include algorithm-execution imitation on polynomial problems [28], control models trained on expert trajectories [55] [56], and GATO's 1.2B-parameter model spanning hundreds of tasks [51].The paper distinguishes GOAL's focus on NP-hard problems and imitation of solutions from specialized solvers.Source: §2 · p. 3

3. Multi-Task Learning for Combinatorial Optimization

GOAL frames multiple tail-recursive combinatorial optimization tasks as a shared learning problem, with task-specific representations and adapters around a shared model. Its architecture incorporates edge features into attention and shares parameters across meaningful combinations of heterogeneous node types.

3.1. Constructive CO problem solving

  • Constructive CO casts solution building as sequential decisions over partial solutions, modeled here with BQ-MDPs whose states are instances and whose actions are construction steps.The paper uses BQ-MDPs for tail-recursive problems, a class it describes as solvable by dynamic programming.Source: §3.1 · pp. 3–4

3.2. Multi-Task CO Problems

  • The multi-task problem combines task identifiers with instances from each task’s parameter space, while task-specific components remain necessary and pure zero-shot generalization is not possible.The paper assumes task similarity may let learning on one task provide skills useful to others.Source: §3.2 · pp. 4–5

3.3. Task Representation

  • GOAL represents a task instance with node and optional edge features, and scores candidate node-option actions; task-dependent masks can exclude disallowed actions.The representation allows features at node, edge, or instance level, and construction steps select a node, optionally with one of a fixed number of options.Source: §3.3 · p. 5

3.4. Architecture of the Model

  • GOAL’s mixed attention adds edge components to node keys and queries, incorporating relational information into attention; its attention matrices have quadratic size in the number of nodes.When available, task-specific heuristics pre-filter nodes before they are presented to the model.Source: §3.4 · pp. 5–6
  • Task-specific low-rank input projections feed a shared codebook that maps node and edge features into the backbone’s embedding space.The low-rank projections are intended to encourage representations from different tasks to share dimensions.Source: §3.4 · pp. 5–6

3.5. Multi-Type Transformer Architecture

  • For heterogeneous graphs, GOAL uses self- and cross-attention blocks on compatible node- and edge-type combinations, with the same layer-specific parameters shared across blocks.For n node types, the architecture can use n² blocks or a task-defined selection of relevant types.Source: §3.5 · p. 6

3.6. Training Procedure

  • Training imitates high-quality solutions from specialized solvers across eight problems, sampling tasks and suffix subproblems in batches.For multi-type tasks, attention and feed-forward blocks are duplicated within each layer while retaining shared parameters.Source: §3.6 · p. 6

4. Experiments

The experiments assess GOAL across its training tasks, transfer to unseen problems, and architectural ablations. Results show strong multi-task performance and effective fine-tuning, while the ablations examine mixed attention, type handling, and codebook sparsification.

4. Experiments

  • The experiments assess shared-backbone performance, unseen-task transfer, and component ablations, training on eight varied COPs with one million instances per task.The training set includes routing, scheduling, knapsack, and vertex-covering problems.Source: §4 · pp. 6–7

4.1. Performance on the Training Tasks

  • Single-task GOAL achieved the best performance on 7 of 8 tasks, while multi-task GOAL was only slightly worse, supporting shared-backbone learning across problems.The comparison is reported for 128 test instances from the training tasks; lower gaps are better.Source: §4.1 · p. 7, Table 1 · p. 8

4.2. Fine-Tuning to New Tasks

  • For eight diverse unseen COPs, unsupervised fine-tuning systematically outperformed unsupervised training from scratch at comparable processing-time budgets; the multi-task model consistently performed as well as or better than the most-related single-task model.Source: §4.2 · pp. 7–8, Figure 3 · p. 9

4.3. Ablation Study

  • On ATSP, mixed-attention improved performance at convergence versus MatNet and convergence speed versus G2G.The ablations used 100k training instances, fewer than the earlier experiments.Source: §4.3 · p. 8
  • After 200 epochs on 100K instances, multi-type GOAL reached a 4.6% test optimality gap versus 8.9% for single-type GOAL.The multi-type architecture also converged faster and can relax parameter sharing during fine-tuning to better fit a task.Source: §4.3 · p. 8
  • In supervised fine-tuning, shared-codebook sparsification produced more stable runs and a better optimality gap, without a significant effect on training-task performance.The reported stability comparison covers 10 runs; the codebook result is shown for PCTSP, with similar results noted for other problems.Source: §4.3 · p. 8

5. Discussion and Conclusion

GOAL uses a shared backbone to address routing, scheduling, packing, and classic graph problems, with task-specific adapters and reported state-of-the-art single-task results on seven CO problems. Its use is bounded by feasibility requirements and the quadratic cost of its transformer architecture.

5. Discussion and Conclusion

  • GOAL uses one shared backbone across routing, scheduling, packing, and graph problems, with reported state-of-the-art single-task results on seven CO problems.The paper also reports multi-task use of the same backbone and fine-tuning to new problems.Source: §5 · p. 9
  • Use is bounded to constructive problems with easily ensured feasibility; quadratic transformer cost is too high beyond 1,000 nodes.The paper identifies more efficient attention as a direction for improving scaling.Source: §5 · p. 9

A. GOAL Hyperparameters and size

B. Supervised fine-tuning of GOAL

Supervised fine-tuning adapts GOAL to eight new problems using 128 solved instances and takes only a few minutes, unlike unsupervised fine-tuning, which averages a few hours.

B. Supervised fine-tuning of GOAL

  • Unsupervised fine-tuning on the eight new problems takes, on average, a few hours.The paper characterizes this transfer mode as useful but expensive.Source: B. Supervised fine-tuning of GOAL · p. 14
  • Supervised fine-tuning adapts GOAL to the same eight new problems using 128 solved instances and takes only a few minutes.Each instance uses one training step per tail-subproblem; instances need not be optimal.Source: B. Supervised fine-tuning of GOAL · p. 14
  • Figure 6 reports the best results over 10 runs for both fine-tuning and training from scratch.The supplied text does not state the plotted result values.Source: Figure 6 · p. 14

C. Impact of codebook on fine-tuning

A shared codebook improves fine-tuning stability and performance across transfer problems, while GOAL’s multi-type mixed-attention blocks adapt attention to scheduling-task relations.

C. Impact of codebook on fine-tuning

D. Multi-type mixed attention layers for UMSP and JSSP

  • In UMSP, absent within-job and within-machine edge information makes those self-attention blocks vanilla, while cross-attention mixes machine execution-time edges.In JSSP, operations have precedence and same-job relations, so the operations self-attention block is mixed.Source: D. Multi-type mixed attention layers… · p. 15
  • Figure 8 illustrates the multi-type model for UMSP and JSSP, distinguishing vanilla multi-head attention (MA) from mixed-attention (MMA).The blocks attend to the meaningful combinations of types described for each scheduling problem.Source: D. Multi-type mixed attention layers… · p. 15

E. Generalization to new instance distributions

GOAL generalizes to instances up to 10 times larger than training instances for a subset of tasks and shows strong optimality-gap generalization on problems with varied edge features.

E. Generalization to new instance distributions

  • The reported larger-instance results cover instances up to 10 times the training size for a subset of training tasks.The table reports lower-is-better results; NCO methods use greedy decoding except where marked, and † solvers did not solve all instances within the time budget.Source: E. Generalization to new instance… · p. 15
  • GOAL takes a bit more time than some baselines, while scaling to much larger instances is not a focus of the paper.The discussion notes quadratic attention complexity and mentions task-specific heuristics or non-quadratic attention as possible alternatives.Source: E. Generalization to new instance… · p. 15
  • GOAL shows excellent optimality-gap generalization on ATSP with an asymmetric distance matrix and JSSP with precedence and job-machine relation matrices.Source: E. Generalization to new instance… · p. 15

F. Description of the considered CO problems

The section describes GOAL’s coverage of routing, scheduling, packing, graph, and location problems and details how instances, features, actions, objectives, and trajectories are represented.

F. Description of the considered CO problems

  • GOAL solves routing, scheduling, packing, graph, and location problems, with representations specifying features, actions, objectives, and solution trajectories where applicable.Source: F. Description of the considered CO… · p. 15
  • Table 2 reports larger-instance generalization with lower values better, noting greedy-decoding exceptions and instances unsolved within the time budget.Source: Table 2 · p. 16

F.1. Capacitated Vehicle Routing Problem and Split-Delivery Capacitated Vehicle Routing Problem

  • CVRP minimizes total fleet travel distance while meeting customer demands and vehicle capacities; SDCVRP permits multiple vehicles to fulfill one customer's demand.GOAL is trained on Euclidean CVRP and fine-tuned on SDCVRP.Source: §F.1 · p. 17
  • For CVRP, GOAL represents capacity as an instance feature, demand as a node feature, and inter-node distance as an edge feature; its actions select nodes directly or via depot.Locations are sampled from the unit square and demands are integers from 1 to 10; capacity varies with problem size.Source: §F.1 · p. 17

F.2. Capacitated Vehicle Routing Problem with Time Windows

The appendix specifies training formulations for CVRPTW, JSSP, and Knapsack, including their objectives, input features, and solution-construction choices.

F.2. Capacitated Vehicle Routing Problem with Time Windows

  • CVRPTW minimizes total travel and serving time subject to vehicle capacities and customer time windows, using remaining capacity and current time as instance features.Locations are sampled from the unit square; customer time windows are generated to ensure feasible instances.Source: §F.2 · p. 17

F.3. Job Shop Scheduling Problem

  • JSSP schedules ordered, non-preemptive job operations on machines to minimize makespan, using operation times and precedence and machine dependencies as graph features.Operation execution times are sampled from U(1, 100); the action selects an operation and the trajectory orders tasks by minimal finishing time.Source: §F.3 · p. 18

F.4. Knapsack Problem

  • Knapsack selects items to maximize total value without exceeding capacity, with item values and weights as node features and remaining capacity as an instance feature.The appendix samples weights and values from the unit interval and sets capacity to 25.Source: §F.4 · p. 18

F.5. Maximal Independent Set Problem

The appendix describes the Maximal Independent Set problem and its fine-tuning setup: GOAL is adapted to random graphs, with adjacency represented as edge features.

F.5. Maximal Independent Set Problem

  • MIS seeks a largest set of mutually nonadjacent vertices, and the paper fine-tunes GOAL to this problem.The appendix generates Erdős–Rényi graphs with edge probability sampled from [0.05, 0.15].Source: §F.5 · p. 18
  • The MIS formulation uses adjacency values as edge features, selects nodes as actions, and has no instance or node features or trajectory order.Its objective is to maximize the number of selected nodes.Source: §F.5 · pp. 18–19

F.6. Maximum Coverage Location Problem

The appendix outlines the formulations and training or fine-tuning settings for coverage, graph, scheduling, and routing problems, including the input features and objectives used for each.

F.6. Maximum Coverage Location Problem

  • MCLP places facilities at locations to maximize covered locations; the appendix fixes 10 facilities and coverage radius 0.1 and uses facility count, radius, and distances as features.GOAL is fine-tuned to MCLP, with facility nodes as actions and no trajectory order.Source: §F.6 · p. 19, §F.5 · p. 19

F.7. Minimum Vertex Cover Problem

  • MVC minimizes the number of vertices covering every edge, while MWVC minimizes their total weight; the appendix uses MIS data generation and features and trains GOAL on MVC..Source: §F.7 · p. 19

F.8. Open Shop Scheduling Problem

  • OSSP schedules operations without a predefined order, avoiding overlap on machines and minimizing makespan or total completion time; its data and features follow JSSP except for precedence constraints..Source: §F.8 · p. 19

F.9. Open Vehicle Routing Problem

  • OCVRP uses an unbounded depot fleet whose vehicles need not return after delivery; the appendix fine-tunes GOAL on its Euclidean version.Its data generation and features follow CVRP.Source: §F.9 · p. 20

F.10. Orienteering Problem

  • Euclidean OP maximizes collected prizes under a travel budget, using remaining distance, prizes, and pairwise distances as features; GOAL is trained on this version.The appendix sets the maximum distance to 4 and samples prizes proportional to distance from the depot.Source: §F.10 · p. 20

F.11. Price Collection Traveling Salesman Problem

  • PCTSP trades off travel distance and penalties for skipped nodes while meeting a minimum-prize constraint; its features include remaining prize constraint, prizes, penalties, and distances.The appendix generates instances following previous work [63].Source: §F.11 · pp. 20–21

F.12. Sequential Ordering Problem; F.13. Traveling Repairman Problem

  • SOP finds a shortest route subject to precedence constraints and is a fine-tuning task; TRP minimizes total delay to visited locations and is fine-tuned on Euclidean instances.SOP uses origin and precedence features; TRP uses origin and distance features, and both use ordered tours.Source: §F.12 · p. 21, §F.13 · p. 21

F.14. Traveling Salesman Problem; F.15. Unrelated Machine Scheduling Problem

  • The appendix trains GOAL on ATSP to minimize tour length, while UMSP assigns jobs to machines with differing processing times to minimize makespan.TSP uses origin/destination and distance features; UMSP uses machine availability and execution-time features, with processing times sampled from U(1, 100).Source: §F.14 · p. 22, §F.15 · p. 22

Related papers

Loading 2406.15079v3…