Source-linked AI summary
Neural Combinatorial Optimization with Reinforcement Learning
Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, Samy Bengio
TL;DR
The paper asks whether neural networks trained with reinforcement learning can tackle combinatorial optimization without relying on optimal labels or heavily handcrafted heuristics. It trains a recurrent stochastic policy with policy gradients and evaluates pretraining and instance-specific search, achieving near-optimal TSP results up to 100 nodes and optimal KnapSack results up to 200 items.
Problem
Combinatorial optimization often requires changing handcrafted heuristics, while supervised learning lacks optimal labels for most problems.
Method
The framework trains a recurrent stochastic policy with policy gradients, using expected tour length as the objective and combining RL pretraining with active search.
Results
The method achieves close to optimal TSP results on 2D Euclidean graphs with up to 100 nodes and optimal KnapSack results for instances with up to 200 items.
Takeaways & Limitations
The results support neural networks with reinforcement learning as a general tool for combinatorial optimization, especially where heuristic design is difficult.
Takeaways & Limitations
The approach is computationally expensive, and feasible-solution construction can be challenging for constrained problems such as TSP with Time Windows.
Abstract
from arXiv · showhide
This paper presents a framework to tackle combinatorial optimization problems using neural networks and reinforcement learning. We focus on the traveling salesman problem (TSP) and train a recurrent network that, given a set of city coordinates, predicts a distribution over different city permutations. Using negative tour length as the reward signal, we optimize the parameters of the recurrent network using a policy gradient method. We compare learning the network parameters on a set of training graphs against learning them on individual test graphs. Despite the computational expense, without much engineering and heuristic designing, Neural Combinatorial Optimization achieves close to optimal results on 2D Euclidean graphs with up to 100 nodes. Applied to the KnapSack, another NP-hard problem, the same method obtains optimal solutions for instances with up to 200 items.
1 INTRODUCTION
The paper frames combinatorial optimization as difficult for handcrafted and supervised methods, then proposes reinforcement learning with neural networks to learn solution policies. It evaluates this framework on TSP and KnapSack, reporting strong results with combined pretraining and active search.
- Motivation: TSP optimization is NP-hard, and handcrafted heuristics often require revision when problem statements change.Machine learning may discover heuristics from training data with less task-specific engineering.
- Motivation: Supervised learning is generally unsuitable because optimal labels are unavailable for most combinatorial optimization problems.The paper instead uses solution-quality comparisons and reward feedback to train an agent.
- Approach: Neural Combinatorial Optimization uses policy gradients to train an RNN policy over solutions, with RL pretraining and active search as its two approaches.Pretraining learns on training graphs, whereas active search optimizes the RNN on each test instance.
- Results: Combining RL pretraining with active search works best in practice.
- Results: On 2D Euclidean graphs with up to 100 nodes, the method significantly outperforms supervised TSP learning and reaches near-optimal results with more computation.The same framework obtains optimal KnapSack results for instances with up to 200 items.
2 PREVIOUS WORK
Prior work spans exact algorithms, handcrafted heuristics, generic solvers, hyper-heuristics, and neural approaches to TSP. These methods motivate a more general optimization system that can learn solution-search strategies across changing problems.
- Classical TSP methods: Christofides’ algorithm runs in polynomial time and guarantees solutions within 1.5× of optimality for metric TSP instances.
- Classical TSP methods: Exact dynamic programming for TSP has complexity Θ(2nn2), making it infeasible for instances with around 40 points.Large-scale exact solvers therefore combine cutting planes and branch-and-bound to prune the search space.
- Generic optimization methods: Generic routing solvers combine local search operators with metaheuristics that propose uphill moves and escape local optima.
- General optimization methods: Hyper-heuristics select or generate heuristics, abstracting part of the knowledge-intensive process of choosing problem-specific search methods.Unlike the proposed approach, they operate on the search space of heuristics rather than directly on solution space.
- Neural approaches: Earlier neural TSP methods include Hopfield networks and deformable templates, but Hopfield approaches are sensitive to hyperparameters and initialization.
- Neural approaches: Pointer Networks revisit TSP with recurrent supervised models that predict visited-city sequences using approximate-solver supervision.
3 NEURAL NETWORK ARCHITECTURE FOR TSP
The TSP model represents tours as permutations of input city points and learns a stochastic policy that favors shorter tours. A pointer-network encoder-decoder uses attention-like pointing to select each next city without a fixed output vocabulary.
- Problem formulation: The 2D Euclidean TSP asks for a permutation that visits every city once while minimizing total tour length.The input graph is a sequence of n cities represented as two-dimensional points.
- Policy representation: The policy p(π | s) assigns higher probability to short tours and lower probability to long tours.
- Policy representation: The tour probability is factorized with the chain rule, and individual softmax modules represent the resulting conditional terms.
- Pointer-network design: A vanilla sequence-to-sequence model cannot generalize beyond its prespecified graph size and requires ground-truth output permutations.The pointer-network design addresses both issues by pointing to positions in the input sequence.
- Architecture details: The pointer network uses recurrent encoder and decoder modules to encode the city sequence and produce a distribution over the next city.The decoder feeds each selected city into the next decoding step.
- Architecture details: Its attention function maps a decoder query and encoder reference vectors to probabilities over references, representing which input position the model points to.
- Architecture details: Using one glimpse in the pointing mechanism improves performance at insignificant latency cost in the experiments.
4 OPTIMIZATION WITH POLICY GRADIENTS
The paper uses policy gradients to train neural policies for combinatorial optimization without requiring optimal supervised labels. It combines pretraining, instance-specific search, and reward-based baselines to improve solution search.
- Motivation: Supervised labels are often unavailable or costly for NP-hard optimization, so the method learns from reward feedback instead.A verifier can compare candidate solutions even when optimal labels are unavailable.
- Policy-gradient objective: The pointer network is optimized to minimize expected tour length over stochastic solutions sampled for input graphs.Training samples graphs from a distribution and uses policy-gradient estimates with stochastic gradient descent.
- Baseline limitation: An exponential moving-average baseline can fail to distinguish input graphs because one shared value may discourage optimal tours on difficult instances.The paper motivates a critic as a graph-dependent alternative to this shared baseline.
- Variance reduction: A critic estimates expected tour length for each input graph, providing a parametric baseline for lower-variance policy-gradient learning.The critic is trained by mean squared error against tour lengths sampled from the current policy.
- Search strategies: Active Search updates the stochastic policy during inference on one test instance, whereas sampling keeps the trained policy fixed and selects the shortest sampled tour.Active Search uses candidate solutions from a single test input; sampling evaluates multiple candidates without updating model parameters.
5 EXPERIMENTS
Experiments evaluate Neural Combinatorial Optimization on randomly generated Euclidean TSP instances using supervised learning, RL pretraining, sampling, and active search. RL methods outperform supervised learning and heuristic baselines, with search improving solution quality at increased computational cost.
- Experimental setup: 1,000 randomly generated graphs were used for each Euclidean TSP benchmark with 20, 50, and 100 nodes.Points were sampled uniformly from the unit square.
- Baselines: The supervised-learning baseline used one million optimal tours but produced suboptimal results, including on TSP100.The authors report that these results were worse than those previously reported by Vinyals et al.
- Methods: RL pretraining used actor-critic updates, while inference evaluated greedy decoding, sampling, and active search configurations.Sampling generated 1,280,000 candidates per test instance; pretrained active search used up to 10,000 steps and the same candidate budget.
- Results: RL training significantly improved over supervised learning, and all proposed methods surpassed Christofides; greedy RL methods were only a few percent worse than optimality.The comparisons report average tour lengths and running times across TSP20, TSP50, and TSP100.
- Results: Inference-time search moved results closer to optimality but increased running time, although search could be stopped early with a small objective tradeoff.The sampling and active-search comparisons vary the number of considered solutions and report corresponding GPU running times.
- Results: Sampling outperformed active search on smaller solution spaces, whereas active search was superior on larger spaces when controlling for sampled solutions or running time.Active search from scratch remained competitive but required 7 and 25 hours per TSP50 and TSP100 instance, respectively.
6 GENERALIZATION TO OTHER PROBLEMS
Neural Combinatorial Optimization extends its reinforcement-learning framework beyond TSP by adapting architectures, rewards, and feasibility handling to other combinatorial problems. On KnapSack, active search reaches optimality on instances with up to 200 items, while feasibility can remain computationally difficult for constrained problems.
- Framework adaptation: The framework adapts model architectures to output permutations, subsets, structured labels, or other problem-specific solution representations.Pointer networks suit permutations, truncated permutations, or subsets; seq2seq models support other structured outputs, while pointer and softmax modules can jointly assign labels.
- Framework adaptation: Training procedures transfer across optimization tasks by adapting the reward function to each problem.
- Feasibility: Feasibility can be enforced by assigning zero probability to branches known to be infeasible during decoding.This approach parallels preventing the TSP pointer mechanism from selecting a city more than once.
- Feasibility: For constrained problems such as TSP with Time Windows, determining feasible branches may require subtree searches nearly as difficult as direct optimization without problem-specific heuristics.
- Feasibility: The method can instead learn constraints through penalties, although this does not guarantee consistently feasible samples at inference time.The paper also suggests combining explicit zero-probability masking for identifiable infeasibility with penalties for completed infeasible solutions.
- KnapSack example: Active Search solves all KNAP50, KNAP100, and KNAP200 instances to optimality, while RL pretraining-Greedy averages 1% below optimal.The datasets each contain 1,000 instances, with item weights and values drawn uniformly from [0, 1].
7 CONCLUSION
The paper presents Neural Combinatorial Optimization as a neural-network and reinforcement-learning framework for combinatorial optimization. Experiments show close-to-optimal performance on 2D Euclidean TSP graphs with up to 100 nodes.
- Neural Combinatorial Optimization uses reinforcement learning and neural networks to tackle combinatorial optimization.
- The framework achieves close to optimal results on 2D Euclidean graphs with up to 100 nodes.
A.1 POINTING AND ATTENDING
The pointing and attending mechanisms construct valid TSP tours by masking visited cities and refining attention-derived representations before producing next-city probabilities.
- Pointing mechanism: The pointing mechanism parameterizes attention scores with two attention matrices and an attention vector.
- Pointing mechanism: At decoder step j, the pointer network assigns probabilities to the next tour point.
- Pointing mechanism: Setting logits for previously visited cities to −∞ ensures that decoded TSP tours contain no repeated cities.
- Attending mechanism: The glimpse function forms a weighted linear combination of reference vectors using attention probabilities and can be applied repeatedly.
- Attending mechanism: Applying the glimpse more than once with the same parameters made learning less likely and barely improved results empirically.
A.2 IMPROVING EXPLORATION
The framework modifies attention logits to control exploration during decoding. Temperature softens the distribution above 1, while logit clipping controls logit range and attention entropy.
- Softmax temperature: Softmax temperature modifies the attention distribution, with T set to 1 during training.
- Softmax temperature: When T > 1, the attention distribution becomes less steep and helps prevent overconfidence.
- Logit clipping: Logit clipping modifies the attention function using a hyperparameter C.
- Logit clipping: C controls the range of logits and therefore the entropy of the attention distribution.
A.3 OR TOOL’S METAHEURISTICS BASELINES FOR TSP
Table 6 reports OR-Tools metaheuristic performance as the number of considered solutions increases, with corresponding runtimes provided in seconds. Figure 3 shows sample TSP50 and TSP100 tours.
- Table 6 evaluates OR-Tools’ metaheuristics while considering more solutions.The table caption frames the comparison around performance at different solution counts.
- The table reports corresponding running times in seconds on a single Intel Haswell CPU.
- Figure 3 presents sample tours for TSP50 and TSP100.