Research map / Optimization / Optimizers
Solving the Asymmetric Traveling Salesman Problem via Trace-Guided Cost Augmentation
Zhen Zhang, Javen Qinfeng Shi, Wee Sun Lee
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a continuous relaxation of the Asymmetric Traveling Salesman Problem using differentiable trace-based acyclicity constraints (DAG penalty) to encourage valid permutations.
Problem
Asymmetric Traveling Salesman Problem (ATSP), a fundamental and hard combinatorial optimization problem, lacks strong continuous relaxations that enforce acyclic, valid tour structures.
Approach
Integrates a differentiable trace-based directed-acyclic-graph (acyclicity) constraint together with permutation-validity constraints into a continuous relaxation, using trace-guided cost augmentation to steer optimization toward valid tours.
Experimental setup
Builds on: NOTEARS-style DAG constraint
Closest papers by meaning
- Unify ML4TSP: Drawing Methodological Principles for TSP and Beyond from Streamlined Design Space of Learning and Search (ICLR 2025 · similarity 0.86)
- DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem (AAAI 2025 · similarity 0.85)
- Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems (ICML 2024 · similarity 0.83)
- Improved Approximation Algorithms for Clustered TSP and Subgroup Planning (AAAI 2025 · similarity 0.83)
- Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems (NeurIPS 2025 · similarity 0.83)
- Differentiable extensions with rounding guarantees for combinatorial optimization over permutations (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
