Information-theoretic formulation of the Traveling Salesman Problem

Abstract

The Traveling Salesman Problem (TSP) asks for the shortest route to visit a set of cities exactly once. It combines a simple local rule - each city must be visited once - with a hard, global constraint- all cities must be traversed within a single cycle. We cast the problem within a probabilistic, information-theoretic framework. The coexistence of local and global constraints is precisely what makes the problem difficult to address in this framework: the local rule can be enforced through vertex-level constraints, whereas the global constraint cannot be captured by independent edge probabilities. We show that this obstacle can be overcome by defining a maximum-entropy probability distribution over graphs, in which edge costs and degree constraints generate an assignment-like ensemble, and a global term, describing the hard constraint, tilts this ensemble toward Hamiltonian cycles. To make the construction tractable, we derive a mean-field approximation in terms of edge occupancies and implement a differentiable cycle penalty that suppresses sub-tours. This leads to a self-consistent numerical procedure whose output is not only a candidate tour but also a probability matrix encoding competing edges and degenerate solutions. We test the method on synthetic ensembles and on TSPLIB instances. The algorithm converges to connected tours in polynomial time, matching the best-known solution in the majority of instances and remaining within a small relative gap otherwise. Beyond its competitive performance, the proposed framework offers a general approach for handling hard constraints while reducing hard combinatorial optimization problems to simpler ones.