Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning

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

Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1911.04936 v1 pith:3GAHUVCL submitted 2019-11-12 cs.LG stat.ML

Qiang Ma , Suwen Ge , Danyang He , Darshan Thaker , Iddo Drori This is my paper · ORCID

classification cs.LGstat.ML

keywords gpnshierarchicalproblemsgraphnetworkspointercombinatorialconstrained

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

read the original abstract

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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

PLATO: Pointer Learner for Agent and Task Openness
cs.AI 2026-07 conditional novelty 6.0 of 10

A pointer-network actor plus GNN critic jointly handles agent and task openness in MARL without fixed bounds, with proofs of well-definedness and strong wildfire results.
BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learning
cs.LG 2024-11 conditional novelty 6.0 of 10

BPQP reformulates the backward pass of differentiable convex optimization layers as an equality-constrained quadratic program, allowing fast ADMM-based solvers to compute gradients.
Using Reinforcement Learning to Guide Graph State Generation for Photonic Quantum Computers
quant-ph 2024-12 conditional novelty 5.0 of 10

An RL/GNN-based compiler (RLGS) finds emitter-based photonic graph-state generation sequences that reduce generation time by up to 57.5%, emitters by up to 17.5%, and CZ gates by up to 57.8% versus a Stabilizer Solver...
Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solvers
cs.LG 2024-11 conditional novelty 5.0 of 10

After per-heatmap tuning of MCTS hyperparameters, a simple k-nearest-neighbor heatmap (GT-Prior) matches or beats learned heatmaps on uniform, shifted-distribution, and TSPLIB benchmarks, while search settings alone s...

Pith tools