Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search

How do humans produce near-optimal solutions to computationally hard combinatorial optimization problems like the Euclidean Traveling Salesman Problem (TSP) under severe time constraints? The authors investigate the cognitive algorithms and computational principles that allow humans to generate high-quality tours, comparing human performance against various neural network policies and heuristic search methods.

The researchers conducted a large-scale behavioral experiment, collecting over 20 million human-generated tours across 150,000 TSP instances (the tsp150k dataset). They evaluated several computational models, including classic heuristics (e.g., Nearest Neighbor, Convex Hull), exact solvers (Concorde), and Pointer Networks. The Pointer Networks were trained using different objectives: supervised learning on optimal tours, reinforcement learning (RL), and a hybrid approach (supervised pretraining followed by RL fine-tuning). These models were then tested using various decoding strategies, such as greedy search, beam search, and Best-of-N sampling, to see which best matched human behavior.

Human tours are not identical to optimal tours but occupy a near-optimal geometric basin, sharing structural properties with optimal solutions while exhibiting systematic human-specific deviations. The study found that models trained solely on optimal tours or solely on human tours were insufficient to capture the full range of human behavior. Instead, the best-performing model was a Pointer Network pretrained on optimal tours and fine-tuned via RL, decoded using Best-of-N sampling. This suggests that human-like performance emerges from a combination of structured learning, reinforcement-based optimization, and test-time search.

This work bridges the gap between cognitive science and artificial intelligence by demonstrating that human problem-solving strategies can be effectively approximated by modern neural architectures. By showing that human-like behavior is not just about imitation but about balancing learned structural priors with active search, the study provides a framework for developing AI systems that are both efficient and aligned with human cognitive patterns.