---
kind: concept
slug: neural-combinatorial-optimization
title: Neural combinatorial optimization
summary: >-
  Learning a policy that builds routes or other discrete solutions one decision at a time, trained by reinforcement learning. One card so far: an attention-based pickup-and-delivery route builder. Author-reported: faster early answers than OR-Tools, close final quality only up to 200 stops, and hours to days of training per model.
tags: [combinatorial-optimization, vehicle-routing, time-windows, reinforcement-learning, attention-model]
papers: ["2608.14156"]
related: [attention-mechanism, metaheuristic-optimization, branch-and-bound, constraint-satisfaction, policy-gradient]
status: draft
updated_at: 2026-10-31
---

## Overview

A combinatorial problem asks for the best arrangement of discrete choices,
such as the order in which vehicles visit stops. The approach here treats the
solution as a sequence of decisions. A neural policy scores the feasible next
choices, and reinforcement learning trains it on sampled instances. Once
trained, the network produces a complete solution by repeating the choice
step, with no search at answer time [arxiv:2608.14156 §3].

The shared invariant is that every step must respect the problem's
constraints. The policy only chooses among actions that break no rule, which
is enforced with masks [arxiv:2608.14156 §3]. Hard feasibility is therefore
built into the action set, not learned.

## Variants

### Attention-based route builder with parallel routes

The only variant covered so far builds several routes at once. The base model
is JAMPR, an extension of the attention model of Kool et al., which adds
encoders for each route and vehicle [arxiv:2608.14156 §2.2, §3]. Card:
[Attention-based pickup-and-delivery route builder](/papers/2608.14156).

The authors add two changes to JAMPR [arxiv:2608.14156 §3]:

- A pickup-order mask: a delivery is offered only after its pickup.
- A soft cost: a missed client adds a penalty instead of making the plan
  infeasible. The cost is 13 per unit of distance plus 10 per missed client.
  The authors chose both weights empirically.

The paper does not say how each delivery is linked to its pickup, whether
routes return to the depot, or what units the coordinates use. Those points
decide the scale of the penalty weights, so a reimplementation must fix them
itself [arxiv:2608.14156 §3, §4].

Not covered by this page: learned partitioning and destruction operators,
which the paper lists as future work [arxiv:2608.14156 §7].

## When to use which

The choice below rests on one paper, with author-reported results against a
single baseline, OR-Tools [arxiv:2608.14156 §5].

| Situation | Use | Why |
|---|---|---|
| Many stops, a fast first answer matters, and the instances resemble the training distribution | A learned route builder of this kind | Better early solutions than OR-Tools at every size tested; up to 3% lower cost in the first seconds at n=50 and a large gain at n=400 and 1000 [arxiv:2608.14156 §5.1, §5.3] |
| Up to about 200 stops and final quality matters | Learned builder or classical solver; the paper reports them as close | Final quality close to OR-Tools only up to 200 customers [arxiv:2608.14156 §5.2, §6] |
| 400 or more stops and final quality matters under a fixed time budget | Classical metaheuristic | At 400 s, the neural answer is about 20% higher than the metaheuristic result [arxiv:2608.14156 §5.3] |
| Little GPU time or a short project | Classical solver | Training takes 3 to 336 hours per model on one A40 [arxiv:2608.14156 tab. 1] |
| Missed clients must make the whole plan fail | Not covered | The paper sets this hard version aside and studies only the soft penalty [arxiv:2608.14156 §3] |
| Instances may drift far from the training distribution | Classical solver, as a safe default | Still better than OR-Tools under a normal-distribution shift only up to about 25% shifted points [arxiv:2608.14156 §5.4] |
| Problems that may not always be feasible | Learned builder with the soft cost | JAMPR solved all test instances, while OR-Tools missed more as n grew [arxiv:2608.14156 §5.4] |

## Implementation sketch

The loop below is written from the description in [arxiv:2608.14156 §3].
The paper gives no algorithm block, so the details marked "not stated" must
come from elsewhere or be chosen and tested by the implementer.

```pseudocode
# Build one solution with a trained policy  [arxiv:2608.14156 §3]
# Penalty: 13 * distance + 10 * missed client  [arxiv:2608.14156 §3]

def build_solution(instance, policy, kappa):
    # Encode all nodes once; the depot index enters the context  [§3]
    node_emb = encoder(instance.node_features)
    # kappa routes grow in parallel; kappa is not stated  [§3]
    routes = [start_route(instance.depot) for _ in range(kappa)]
    while unvisited_nodes_remain(routes, instance):
        # Keep only (route, node) pairs that break no rule: capacity,
        # time window, visited, pickup before delivery  [§3]
        actions = feasible_actions(routes, instance)
        # Route and vehicle state (load, node, time) feed the context  [§3]
        context = build_context(routes, node_emb, instance.depot)
        # Greedy or sampled choice; decoding at test is not stated  [§3]
        chosen = select(actions, policy(actions, context))
        append_node(routes[chosen.route], chosen.node)
    return routes
```

Training, as the paper describes it, samples fresh instances from a fixed
distribution and stops when the path cost stops falling over 10 optimization
steps [arxiv:2608.14156 §4, §5.2]. The optimizer, learning rate, batch size,
embedding size and baseline are not stated [arxiv:2608.14156 §3].

## Contradictions

None known across the cited papers. Only one paper is covered so far.

Within that paper, the abstract and conclusions call the small and medium
solutions "optimal". The only reference is OR-Tools, and no exact solver is
reported, so that wording is not verified [arxiv:2608.14156 §5.1, §6].

## Papers

- [Attention-based pickup-and-delivery route builder](/papers/2608.14156): attention-based route builder (JAMPR) adapted to pickup-and-delivery routing with capacity and time windows, using a pickup-order mask and a soft penalty.