PaperlayerView exact revision on arXiv

Source-linked AI summary

POMO: Policy Optimization with Multiple Optima for Reinforcement Learning

Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, Seungjai Min

arXiv:2010.16011v3cs.LG

TL;DR

CO problems lack readily available optimal labels and often require hand-crafted heuristics despite changing constraints. POMO uses symmetry-aware multiple rollouts, a low-variance policy-gradient baseline, and augmented greedy inference across TSP, CVRP, and KP. Across these problems, it reports state-of-the-art optimality-gap and inference-time performance, including a 0.14% gap on TSP100.

  • Problem

    Rapidly changing and problem-specific CO constraints make uniformly applicable algorithms difficult, while optimal labels are generally unavailable for supervised learning.

  • Method

    POMO exploits multiple optimal representations through parallel diverse rollouts, a low-variance policy-gradient baseline, and instance augmentation with multiple greedy inference trajectories.

  • Results

    Across TSP, CVRP, and KP, POMO achieves state-of-the-art optimality-gap and inference-time performance; on TSP100, it reaches a 0.14% optimality gap.

  • Takeaways & Limitations

    POMO provides a purely data-driven solver framework that avoids problem-specific hand-crafted heuristics across three NP-hard CO problems.

  • Takeaways & Limitations

    In CVRP, not all nodes are good starting points, but POMO uses all nodes because identifying good starts requires knowing the optimum; instance augmentation can also be limited by available starts.

Abstract

from arXiv · show

In neural combinatorial optimization (CO), reinforcement learning (RL) can turn a deep neural net into a fast, powerful heuristic solver of NP-hard problems. This approach has a great potential in practical applications because it allows near-optimal solutions to be found without expert guides armed with substantial domain knowledge. We introduce Policy Optimization with Multiple Optima (POMO), an end-to-end approach for building such a heuristic solver. POMO is applicable to a wide range of CO problems. It is designed to exploit the symmetries in the representation of a CO solution. POMO uses a modified REINFORCE algorithm that forces diverse rollouts towards all optimal solutions. Empirically, the low-variance baseline of POMO makes RL training fast and stable, and it is more resistant to local minima compared to previous approaches. We also introduce a new augmentation-based inference method, which accompanies POMO nicely. We demonstrate the effectiveness of POMO by solving three popular NP-hard problems, namely, traveling salesman (TSP), capacitated vehicle routing (CVRP), and 0-1 knapsack (KP). For all three, our solver based on POMO shows a significant improvement in performance over all recent learned heuristics. In particular, we achieve the optimality gap of 0.14% with TSP100 while reducing inference time by more than an order of magnitude.

1 Introduction

CO problems are widespread and rapidly changing, making uniform algorithms difficult; POMO addresses this with a data-driven RL framework that exploits solution symmetries across several NP-hard problems.

  • Motivation: CO spans logistics, manufacturing, distribution, and resource allocation, but rapidly changing constraints make uniformly applicable algorithms difficult.Industries therefore commonly rely on hand-crafted heuristics designed by local experts.
  • Motivation: Supervised learning is poorly suited to CO because optimal labels are generally unavailable, whereas solution scores are readily calculable for reinforcement learning.The paper positions RL as a natural training paradigm for CO models.
  • POMO: POMO is a simple, general framework that uses symmetry in sequential CO representations and applies one policy approach across TSP, CVRP, and KP.The framework is designed to generate solvers automatically without problem-specific hand-crafted heuristics.
  • Results: Experiments report superior reductions in optimality gap and inference time against contemporary neural RL approaches.The evaluation covers three NP-hard problems using the same neural network and training method.
  • Contributions: POMO identifies multiple-optimum symmetries, trains with parallel rollouts targeting different optima, and introduces a low-variance policy-gradient baseline.Its contributions also include multiple greedy rollouts and instance augmentation for inference.

2 Related work

Related work includes recurrent, attention-based, value-based, and improvement-oriented deep RL methods for CO, along with inference procedures that generate or refine multiple candidate solutions.

  • Deep RL construction methods: Pointer Network methods use sequence-to-sequence attention architectures with actor-critic training for neural combinatorial optimization.These approaches demonstrated close-to-optimal results for TSP and KP.
  • Deep RL construction methods: Attention Model replaces recurrent architectures with Transformers and trains with REINFORCE using a greedy rollout baseline.It has been applied to TSP, orienteering, and vehicle-routing problems.
  • Deep RL construction methods: Struct2Vec-based methods embed partial solutions as graphs and use deep Q-learning to estimate graph values.Reported applications include TSP, minimum vertex cut, and maximum cut.
  • Inference techniques: Inference methods include active search, sampling, beam search, and classical heuristic post-processing to improve neural solutions.Sampling selects the best among multiple solution candidates, while active search optimizes on one test instance.
  • Deep RL improvement methods: Improvement methods train neural networks to guide local search that iteratively improves solutions within a time budget, unlike POMO’s one-shot construction approach.The paper notes that improvement heuristics built on POMO remain a possible research direction.
  • Solution representations: A five-node TSP can have one unique optimal tour but multiple equivalent node-sequence representations.This representational multiplicity motivates methods that account for solution symmetries.

3 Motivation

A policy network autoregressively constructs CO solutions from node selections conditioned on the problem state. Because equivalent solutions can have different sequence representations, the starting action can disproportionately shape the resulting trajectory.

  • Sequential policy generation: A trainable policy network generates a valid solution τ=(a1,...,aM) by selecting nodes autoregressively one action at a time.The policy conditions later actions on the previously selected actions.
  • Sequential policy generation: The problem instance defines the state s used by the policy during solution generation.The policy is parameterized by θ.
  • Multiple optima: Routing loops and item sets can yield multiple sequence forms for one solution; in TSP, cyclic shifts represent the same optimal tour.For example, (v2,v3,v4,v5,v1) is equivalent to (v1,v2,v3,v4,v5).
  • Motivation: Although equivalent sequences should be treated equally, the starting action a1 strongly influences subsequent actions in the autoregressive policy.The paper identifies this mismatch as a motivation for POMO.

4 Policy Optimization with Multiple Optima (POMO)

POMO exploits multiple equivalent sequence representations by generating parallel trajectories from different starting nodes, then trains them with a shared policy-gradient baseline. At inference, it combines multiple greedy rollouts with optional instance augmentation to improve solution selection.

  • 4.1 Explorations from multiple starting nodes: POMO generates N solution trajectories in parallel, assigning each a different starting node rather than using a single START-token trajectory.The trajectories are sampled by Monte Carlo and represented as sequences of actions.
  • 4.1 Explorations from multiple starting nodes: Equivalent node-sequence representations let POMO explore multiple optimal solutions instead of repeatedly following one START-token path.For routing problems with loops, changing the first node can preserve the same solution while producing a different sequence representation.
  • 4.1 Explorations from multiple starting nodes: POMO directly maximizes first-action entropy by forcing multiple trajectories to contribute equally during training.This avoids favoring particular starting points when several first moves are equally good.
  • 4.2 A shared baseline for policy gradients: POMO uses a shared baseline for every trajectory, computed from the average return across the N sampled trajectories.The baseline reduces gradient variance and makes each trajectory compete with heterogeneous alternatives.
  • 4.2 A shared baseline for policy gradients: The shared baseline makes training more resistant to local minima and has lower policy-gradient variance than the greedy-rollout baseline.Its advantage term has zero mean, and it can be computed without an additional critic or cloned policy forward pass.
  • 4.3 Multiple greedy trajectories for inference: At inference, POMO selects the best among multiple deterministic greedy trajectories generated from different starting nodes.These N greedy trajectories are reported as superior in most cases to N sampled trajectories.
  • 4.3 Multiple greedy trajectories for inference: Instance augmentation reformulates a problem through transformations such as coordinate flips or rotations, enabling additional greedy trajectories for the same solution.Its applicability and multiplicative benefit depend on the CO problem and policy-network model.
  • 4.3 Multiple greedy trajectories for inference: Algorithm 2 combines input augmentation with multiple starting nodes and chooses the highest-return trajectory across transformed instances.The inference procedure accepts the number of starting nodes N and transforms K.

5 Experiments

Experiments evaluate POMO across TSP, CVRP, and KP using a shared Attention Model and standardized training and inference setups. POMO achieves strong solution quality, stable training, and faster inference, while CVRP retains a starting-node limitation.

  • Experimental setup: POMO experiments use the Attention Model, with one encoding pass shared across multiple trajectories generated by stacked decoder queries.POMO is presented as general reinforcement-learning method rather than a method tied to one policy-network structure.
  • Experimental setup: All experiments use prescribed problem setups, randomly generated training instances, and reported inference times for 10,000 random instances.Training uses batches of 64, while routing experiments include inference with and without ×8 instance augmentation; KP uses no augmentation.
  • Traveling salesman problem: 0.14% optimality gap: POMO solves TSP100 in one minute and outperforms all other learning-based heuristics in quality and solving time.For TSP20 and TSP50, reported gaps are 0.0006% in seconds and 0.025% in tens of seconds, respectively.
  • Traveling salesman problem: 3.51% to 1.07%: with identical network structure and inference, the TSP100 gap improvement isolates POMO training as the difference.Multiple greedy rollouts combined with ×8 augmentation reduce the gap further by an order of magnitude.
  • Traveling salesman problem: POMO training is more stable and sample-efficient than simple REINFORCE while taking comparable per-epoch time through parallel trajectory generation.For TSP100, reported training time is about 7 minutes per POMO epoch versus 6 minutes for REINFORCE, despite POMO using N-times more trajectories.
  • Capacitated vehicle routing problem: CVRP experiments use all nodes as starting points, including nodes that cannot begin optimal trajectories, because identifying good starting nodes requires knowing an optimal solution.A secondary network for candidate starting nodes is left for future research.
  • Capacitated vehicle routing problem: 0.32% versus 0.45%: POMO’s CVRP optimality gap is smaller for CVRP100 than CVRP50 relative to LKH3, while outperforming simple REINFORCE by a large margin.The comparison uses LKH3 because no algorithm can find optimal solutions for 10,000 random CVRP instances in reasonable time.
  • 0-1 knapsack problem: POMO improves solution quality over dynamic-programming optima, greedy heuristics, PtrNet, and the original Attention Model in the KP comparisons.The reported improvement holds even without instance augmentation.

6 Conclusion

POMO is a purely data-driven deep-RL approach that exploits multiple optimal solutions during training and inference. Across TSP, CVRP, and KP, it achieves state-of-the-art optimality gaps and inference times, although an earlier runtime report was corrected.

  • POMO avoids hand-crafted heuristics and uses multiple optimal solutions to guide training and inference.The approach was evaluated on TSP, CVRP, and KP.
  • Earlier versions reported incorrect L2I runtimes in Table 3 because single-instance runtimes were used instead of runtimes for 10k instances.

A.1 Application Ideas

The appendix describes instance and input-order transformations that can extend POMO’s augmentation strategy beyond the ×8 coordinate transformations used in the experiments. Their usefulness depends on problem geometry and neural-network architecture.

  • Coordinate transformation: The paper’s coordinate transformations preserve the unit-square range of node locations, keeping augmented TSP and CVRP instances valid under the experimental setup.
  • Coordinate transformation: Rotations, translations, scaling, and flips can generate additional augmentations for Euclidean-distance CO problems.Some transformations may produce non-complying instances, but can still preserve useful near-optimal node orderings.
  • Input ordering: For recurrent or position-sensitive models, reordering the input set provides another instance augmentation because the optimal solution is input-order invariant.Input reordering can yield N! augmentations, potentially exceeding the ×8 coordinate transformations.

A.2 Ablation study without POMO training

Instance augmentation is presented as a general inference technique, and additional experiments show that it can substantially improve a REINFORCE-trained AM network without POMO training. The appendix also specifies the shared model and problem-specific adaptations.

  • Ablation study without POMO training: Instance augmentation is a general inference technique applicable beyond POMO-trained construction-type solvers, including improvement-type deep-RL CO methods.
  • Ablation study without POMO training: ×8 augmentation improves the original AM result to a level similar to sampling 1280 trajectories.The comparison selects the best of eight greedy trajectories.
  • Policy network: The AM decoder uses a context embedding based on the mean embedding and selected-node embeddings, while POMO omits decoder-based selection of the first node.At t = 1, POMO directly defines the first policy selection from node embeddings.
  • Policy network: The shared model uses 128-dimensional node embeddings, six attention layers, eight heads, and 16-dimensional key, value, and query vectors.The same hyperparameters are used for TSP, CVRP, and KP.
  • Policy network: POMO uses N context embeddings and generates trajectories by assigning different starting customer nodes in CVRP.The encoder produces node embeddings and their mean; CVRP trajectories begin after the fixed depot.
  • Policy network: For CVRP parallel rollouts, finished routes remain at the depot with probability 1 until all trajectories finish.This equalizes trajectory lengths for parallel processing.

D.1 Problem setup

The knapsack setup samples item weights and values and seeks the highest-value feasible subset. Its policy adapts TSP processing by masking infeasible items and using total selected value as reward.

  • Problem setup: The KP goal is to select a subset maximizing total value while respecting the knapsack capacity.Weights and values are randomly sampled for N items.
  • Problem setup: The TSP neural net is reused for KP because both problems represent inputs as N two-dimensional tuples.For KP, tuple coordinates represent item weight and value rather than node location.
  • Problem setup: KP masks both selected items and items exceeding the remaining capacity, and episodes end when no remaining item fits.
  • Problem setup: KP uses total selected value as the reward, unlike TSP, which uses negative tour length.

E Our implementation of the original AM

The original AM results in this paper are slightly better than those originally reported for both TSP and CVRP, mainly because training continued until convergence.

  • Slightly better results than the original AM paper were obtained for both TSP and CVRP.
  • The main reason for the improvement was continuing training until the training curve converged.
  • The implementation updates the critic network after every training epoch, without performance-based update logic.
  • The implementation uses six attention layers instead of the original AM paper’s three, giving the compared AM models the same structure.
  • All problems use a fixed batch size of 256 instances, followed by one-time learning-rate decay after convergence.
Loading 2010.16011v3…