PaperlayerView exact revision on arXiv

Source-linked AI summary

Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning

Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, Iddo Drori

arXiv:1911.04936v1cs.LGstat.ML

TL;DR

The paper addresses scalable approximation for TSP and constrained combinatorial optimization, where routing relationships and constraints challenge existing approaches. It introduces graph pointer networks and hierarchical RL, reporting strong larger-scale generalization and competitive constrained solutions. The authors also release data, models, and code publicly.

  • Problem

    Existing routing models do not fully capture relationships between problem entities, while constrained problems such as TSP with time windows remain insufficiently considered and penalty training can be unstable.

  • Method

    The paper extends pointer networks with graph embedding layers and uses hierarchical RL with separate task layers to solve constrained TSP problems.

  • Results

    GPNs generalize from small-scale training to larger-scale TSP, while hierarchical RL produces feasible constrained solutions that outperform previous baselines.

  • Takeaways & Limitations

    GPNs can serve as effective initialization methods for large-scale TSP, and hierarchical RL extends the approach to constrained routing problems.

  • Takeaways & Limitations

    The TSP with time-window data are generated so that feasible solutions always exist, limiting the evaluated setting.

Abstract

from arXiv · show

In this work, we introduce Graph Pointer Networks (GPNs) trained using reinforcement learning (RL) for tackling the traveling salesman problem (TSP). GPNs build upon Pointer Networks by introducing a graph embedding layer on the input, which captures relationships between nodes. Furthermore, to approximate solutions to constrained combinatorial optimization problems such as the TSP with time windows, we train hierarchical GPNs (HGPNs) using RL, which learns a hierarchical policy to find an optimal city permutation under constraints. Each layer of the hierarchy is designed with a separate reward function, resulting in stable training. Our results demonstrate that GPNs trained on small-scale TSP50/100 problems generalize well to larger-scale TSP500/1000 problems, with shorter tour lengths and faster computational times. We verify that for constrained TSP problems such as the TSP with time windows, the feasible solutions found via hierarchical RL training outperform previous baselines. In the spirit of reproducible research we make our data, models, and code publicly available.

1 INTRODUCTION

The paper targets TSP approximation with graph-aware neural networks and constrained optimization with hierarchical reinforcement learning. It proposes GPNs and HGPNs to improve scalability, training stability, and constrained feasibility.

  • Motivation: The TSP requires visiting every city exactly once while minimizing total tour length and is NP-complete.Approximation algorithms and heuristics are used to address the difficulty of finding efficient exact polynomial-time solutions.
  • Prior approaches: Pointer-network RL approaches sample city permutations and previously outperformed most heuristics on TSP instances with up to 100 nodes.The model uses an LSTM encoder, attention decoder, and negative tour length as the reward.
  • Motivation: Existing neural architectures do not fully model relationships between routing-problem entities, motivating graph neural network-based approaches.The paper positions graph information as important for routing and other combinatorial optimization problems.
  • Constrained optimization: Constrained problems such as TSP with time windows remain insufficiently addressed, while penalty-based RL can produce unstable training and difficult hyperparameter tuning.Hierarchical RL instead decomposes complex constrained tasks into simpler subtasks learned across layers.
  • Contributions: The proposed GPN adds graph embedding layers to pointer networks, while HGPNs use hierarchical RL to solve constrained TSP tasks.The work also adds vector context and early stopping to generalize from TSP50 to larger instances such as TSP1000.
  • Evaluation: The experiments evaluate small-scale TSP, generalization to large-scale TSP, and performance on TSP with time windows.The paper is organized around preliminaries, hierarchical RL, GPN architecture, and experiments.

2 PRELIMINARIES

The paper formulates symmetric Euclidean TSP as constrained permutation optimization and casts route construction as reinforcement learning. States contain visited cities, actions select the next city, and policies optimize expected tour cost.

  • TSP formulation: The symmetric 2-D Euclidean TSP seeks a permutation visiting each city exactly once while minimizing total route distance.Its graph is complete and undirected, and the route returns to its starting city.
  • Constrained TSP: The constrained TSP adds constraint functions to the permutation optimization problem.The formulation uses f(σ, X) and g(σ, X) to represent constraint functions.
  • RL formulation: In the RL formulation, a state is the set of previously visited cities and an action selects the next city.The final action selects the start city because the route is cyclic.
  • RL formulation: The policy assigns probabilities to unvisited candidate cities, with trainable neural-network parameters θ defining the policy.The policy distribution determines the next-city choice from the current visited-city state.
  • RL objective: Policy-gradient learning maximizes expected reward, which requires learning a policy that minimizes expected tour length.The permutation distribution is predicted by the neural network.

3 HIERARCHICAL REINFORCEMENT LEARNING

The hierarchical RL framework decomposes constrained TSP optimization into layered policies with distinct roles, latent-variable communication, and layer-specific rewards. Policies are trained bottom-up with policy gradients and central self-critic baselines to improve convergence.

  • Hierarchical policy design: Each layer samples actions from a policy and, except the highest layer, provides latent variables to the next higher layer.The lowest layer is an MDP; middle layers use lower-layer latents and provide higher-layer latents, while the highest layer only consumes a lower-layer latent.
  • Hierarchical policy design: Layer-specific reward functions assign feasibility-related rewards to lower layers and the original optimization objective to higher layers.The experiments use this formulation because it yields better results than ordering layers by increasing optimization difficulty.
  • Hierarchical policy design: Hierarchical RL splits constrained TSP optimization into simpler subproblems learned across layers.Lower layers bias solutions toward feasibility, while higher layers optimize the original objective.
  • Hierarchical policy optimization: The hierarchical policy is learned with REINFORCE-style policy gradients, where each layer optimizes its own reward using a layer-specific baseline and lower-layer latent variables.Parameters are updated by gradient ascent using the objective and gradient defined for each hierarchical layer.
  • Hierarchical policy optimization: The central self-critic baseline uses the reward gap between sampled and greedy actions to center the advantage term and accelerate convergence.The baseline compares sampling and greedy approaches and is reported to converge faster than an exponential moving average of rewards.
  • Hierarchical policy optimization: Training proceeds bottom-up: lower-layer policies are trained first, their network weights are fixed, and higher-layer policies are then learned from supplied latent variables.Algorithm 1 describes layer-wise policy optimization across training steps, batches, and learning rates.

4 GRAPH POINTER NETWORK

The GPN extends pointer networks with graph-based context encoding and uses an attention decoder to construct TSP tours. Its hierarchical version combines layer-specific pointer outputs so lower-level information guides higher-level city selection.

  • GPN Architecture: The proposed GPN is designed to approximately solve the TSP, while vector context supports transfer to larger-scale TSP instances.The paper reports that vector context yields more transferable representations and enables good performance on larger-scale TSP.
  • GPN Architecture: The GPN encoder combines an LSTM point encoder for the current city with a GNN graph encoder for all city coordinates.The point encoder shares coordinate-embedding weights across cities, while the graph encoder captures neighborhood context.
  • GPN Architecture: Vector context represents each city relative to the current city before graph embedding, replacing direct coordinate-based context for larger-scale problems.For current city x_i, each row of the vector context points from node i to another node.
  • GPN Architecture: The attention decoder produces pointer vectors, converts them into a softmax policy over candidate cities, and samples or greedily selects the next visited city.The decoder uses the LSTM hidden state as a query and graph-encoded context as references.
  • Hierarchical GPN Architecture: A two-layer HGPN adds the lower-layer pointer vector to the higher-layer pointer vector when predicting the next candidate city.The lower layer supplies information that acts as a prior for the higher layer.

5 EXPERIMENTS

Experiments evaluate GPN on small and larger-scale TSP instances, then assess HGPN on constrained TSP with time windows. Results show strong transfer to larger instances and higher feasibility for HGPN than baselines.

  • Experimental setup: GPN models use three graph embedding layers, with point context for small-scale problems and vector context for larger-scale problems.Training data is generated online from a uniform distribution, using a central self-critic baseline during reinforcement learning.
  • Small-scale TSP: The small-scale experiments compare GPN against Attention Model, s2v-DQN, Pointer Network, 2-opt, Christofides, and random insertion using approximate optimality gaps.Smaller gaps indicate better results, with optimal solutions obtained using LKH.
  • Larger-scale TSP: GPN generalizes from TSP50 training instances to TSP250/500/750/1000, and GPN+2opt saves ≈20% running time versus s2v-DQN at similar tour length.GPN+2opt also uses ≈25% less running time than 2opt and outperforms OR-Tools on TSP1000, while not surpassing LKH or Farthest Insertion.
  • Larger-scale TSP: Training on larger TSP instances improves predictions on TSP500/1000, with generalization extending roughly an order of magnitude beyond training size.Models trained on TSP20/50/100 are evaluated on TSP500/1000.
  • TSP with time windows: The TSPTW dataset construction guarantees feasible solutions by deriving entering and leaving windows around approximate 2-opt arrival times.The setup uses ei = max{˜ci−˜ei, 0} and li = ˜ci+˜li, ensuring ei ≤˜ci ≤li.
  • TSP with time windows: HGPN outperforms all listed baselines on TSPTW20 and achieves a much higher percentage of feasible solutions than single-layer GPN and other baselines.Results are averaged over 10000 instances, with greedy and sampling inference; sampling 100 or 500 times improves results.

6 DISCUSSION

Discussion focuses on design choices that support generalization and stable constrained-TSP training. Vector context improves large-scale performance, while hierarchical rewards stabilize early TSPTW learning.

  • Generalization: Vector context supplies pairwise information between the current city and all others, and performs better than point context on larger-scale TSP.The comparison is illustrated by GPN validation curves on TSP500.
  • Generalization: Early stopping trains GPN for 10 epochs on TSP50 before predicting TSP500/1000 to improve generalization and avoid overfitting.The study compares performance across different early-stopping levels and trains competing models for 100 epochs.
  • Implementation choices: The pointer-vector clipping range is increased from C = 10 to C = 100 to support a different exploration-exploitation tradeoff.The paper attributes the prior value C = 10 to previous work and selects C = 100 for its model.
  • Hierarchical training: HGPN separates constraint-violation penalties from the TSPTW objective, allowing the lower layer to converge quickly within one epoch.Single-layer GPN combines both terms and shows unstable early training, whereas HGPN trains the higher layer after the lower layer.

7 CONCLUSION

The paper presents GPN as an efficient graph-embedded approach for larger-scale TSP and extends it with hierarchical reinforcement learning for constrained optimization. Experiments report stronger generalization and constrained-TSP performance than previous RL methods.

  • Conclusion: GPN uses graph embedding layers to efficiently solve larger-scale TSP, while hierarchical RL extends the framework to constrained problems such as TSP with time windows.The authors report that data, models, and code are publicly available.
Loading 1911.04936v1…