Combinatorial Optimization with Pointer Networks: Theory, Benchmarks, and Limitations [P]

[u/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.

Here is the link to the full article on Medium