Solving the Asymmetric Traveling Salesman Problem via Trace-Guided Cost Augmentation

The Asymmetric Traveling Salesman Problem (ATSP) is one of the most fundamental and notoriously challenging problems in combinatorial optimization. We propose a novel continuous relaxation framework for ATSP that leverages differentiable constraints to encourage acyclic structures and valid permutations. Our approach integrates a differentiable trace-based Directed Acyclic Graph (DAG) constraint with a doubly stochastic matrix relaxation of the assignment problem, enabling gradient-based optimization over soft permutations. We further develop a projected exponentiated-gradient method with adaptive step size to minimize tour cost while satisfying the relaxed constraints. To recover high-quality discrete tours, we introduce a greedy post-processing procedure that iteratively eliminates subtours through cost-aware cycle merging. Empirically, our method achieves state-of-the-art performance on standard asymmetric TSP benchmarks and demonstrates strong scalability and accuracy, particularly on large or highly asymmetric instances where heuristic solvers such as LKH-3 often struggle.