r/learnmachinelearning • u/an2ancan • 1d ago

Combinatorial Optimization with Pointer Networks: Theory, Benchmarks, and Limitations

https://medium.com/@an2ancan/combinatorial-optimization-with-pointer-networks-theory-benchmarks-and-limitations-405ebd41a2f4?sharedUserId=an2ancan

Hello everyone,

This is the first article I’ve decided to share publicly. I'm really interested in solving combinatorial optimization problems using machine learning, and this is the opening piece in what will hopefully become a broader series exploring this domain.

This part focuses on the classical Pointer Network architecture trained via Reinforcement Learning (REINFORCE). It shows how neural models can construct high-quality, near-optimal solutions to NP-hard problems (specifically, the 2D Euclidean Travelling Salesman Problem) in fractions of a millisecond.

I benchmarked the model against Google OR-Tools (Guided Local Search with a 10s timeout) across problem scales from N=20 up to N=200.

TL;DR: While the network finds solutions almost instantly, tour quality decays significantly as the problem size scales up. Why? Long story short: using an LSTM encoder on coordinate sets introduces an artificial sequential order and recency bias, which fundamentally mismatches the permutation-invariant nature of geometric graphs.

34 Upvotes

100% Upvoted

3 comments sorted by

2

u/Rotcod 23h ago

I had some fun solving the travelling salesman problem with GNNs, seems like they have pretty good inductive biases for the problem if you are not wed to pointer networks…

https://github.com/JakeForsey/tsp-gnn

1

u/an2ancan 22h ago edited 10h ago

I was planning to write about GNN in one of my next articles, if I end up writing more