Per-instance TSP Solver with No Pre-training (1.66% gap on d1291)
Get picks like this daily. Today's launch numbers, the top launches, AI and tech news, and a daily opportunity pick, straight to your inbox.
Want to reach these readers? Sponsor an issue.
OP here.Most Deep Learning approaches for TSP rely on pre-training with large-scale datasets. I wanted to see if a solver could learn "on the fly" for a specific instance without any priors from other problems.I built a solver using PPO that learns from scratch per instance. It achieved a 1.66% gap on TSPLIB d1291 in about 5.6 hours on a single A100.The Core Idea: My hypothesis was that while optimal solutions are mostly composed of 'minimum edges' (nearest neighbors), the actual difficulty comes from a small number of 'exception edges' outside of that local scope.Instead of pre-training, I designed an inductive bias based on the topological/geometric structure of these exception edges. The agent receives guides on which edges are likely promising based on micro/macro structures, and PPO fills in the gaps through trial and error.It is interesting to see RL reach this level without a dataset. I have open-sourced the code and a Colab notebook for anyone who wants to verify the results or tinker with the 'exception edge' hypothesis.Code & Colab: https://github.com/jivaprime/TSP_exception-edgeHappy to answer any questions about the geometric priors or the PPO implementation!
HN · launched Dec 29, 2025 · 21 upvotes (top 34%) · 1 view
Niche: mathematical solvers and optimization engines · 80 launches, 2 in the last 7 days · Explore this niche →
Category and tags
- Horizontal
- Dev tools
- Developer
- AI-native
- Hobby / open-source project
More like this: all 80 launches in mathematical solvers and optimization engines →
Could you build this?
No Designing an un-pretrained, per-instance reinforcement learning solver using PPO that achieves near-optimal TSP solutions requires deep, non-trivial machine learning research and algorithm design.
What it would actually take: A production version requires PyTorch/JAX combined with custom CUDA/C++ graph traversal kernels to rapidly simulate environments for a single TSP instance. The hard part is designing the policy representation, action space parametrization, and reward shaping to ensure PPO converges rapidly without collapsing into local minima or requiring huge offline datasets. This requires advanced expertise in deep reinforcement learning, combinatorial optimization, and GPU kernel acceleration.
Discussion
5 comments analyzed.
Competitors mentioned: LKH3, Concorde solver
Concerns raised: 1200 node TSP is too small/toy problem, Much slower than existing solvers on standard instances, RL not suitable for deterministic TSP problems
Competitors
Other products that read as similar to this one : 73 launches clear the similarity bar, closest 8 shown.
Attention rank: #20 of 74 (itself plus its competitors, highest first, normalized so YC and Product Hunt are compared fairly).
Launched 34 days after the earliest competitor.
- TheoremSmith: Mass-Producing Hard Proof Problems to Train LLMs · hn · 2026-11-10 · 10 upvotes · similarity 0.38
- We scored 50k PRs with AI · hn · 2026-03-30 · 11 upvotes · similarity 0.37
- Flow Matching model inference in C · hn · 2026-07-23 · 5 upvotes · similarity 0.37
- The Hessian of tall-skinny networks is easy to invert · hn · 2026-01-15 · 31 upvotes · similarity 0.37
- learned_index_lab · github · 2026-10-15 · 147 upvotes · similarity 0.37
- TabPFN MCP, gives LLMs tools for predictions on tabular data (beta) · hn · 2026-02-05 · 11 upvotes · similarity 0.35
- Tensor Spy: inspect NumPy and PyTorch tensors in the browser, no upload · hn · 2026-03-02 · 22 upvotes · similarity 0.35
- zkGolf · hn · 2026-07-02 · 69 upvotes · similarity 0.35
The niche, labels, vibe code rating and competitor comparison on this page are analysis by Nicheloom. If you use them, please credit nicheloom.com. How you may use our data.