pith. sign in

arxiv: 2604.06406 · v1 · submitted 2026-04-07 · 📡 eess.SY · cs.SY

Augmented Graphs of Convex Sets and the Traveling Salesman Problem

Gael Luna , Tyler Summers This is my paper

Pith reviewed 2026-05-10 18:43 UTC · model grok-4.3

classification 📡 eess.SY cs.SY
keywords traveling salesman problemgraph of convex setstrajectory optimizationshortest path problembranch and bound1-treesBellman-Held-Karp algorithm
0
0 comments X

The pith

The traveling salesman problem can be encoded exactly in an augmented graph of convex sets and solved as a shortest path problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops a trajectory optimization method for the traveling salesman problem using graphs of convex sets. By augmenting the graph structure, the TSP's requirement to visit each set exactly once is incorporated directly into the model. The result is that the optimal tour becomes equivalent to the shortest path through this augmented graph, which can be found using standard optimization techniques. The approach is shown to relate directly to the Bellman-Held-Karp dynamic programming algorithm for TSP. For larger instances, a branch-and-bound method with 1-tree bounds provides scalable near-optimal solutions.

Core claim

Our framework uses an augmented graph of convex sets to encode the TSP specification and solve it exactly as a shortest path problem in GCS. We establish a precise relationship between the landmark Bellman-Held-Karp algorithm and the augmented graph of convex sets with a TSP specification. Additionally, we present a branch and bound heuristic that uses minimum 1-trees to obtain certifiably optimal or near optimal solutions and scales to problems far larger than the exact framework can handle.

What carries the argument

The augmented graph of convex sets with TSP specification, which incorporates visiting constraints to reduce the combinatorial TSP to an exact shortest-path problem in the continuous GCS framework.

If this is right

  • TSP instances can be solved exactly by finding a shortest path in the augmented GCS without explicit enumeration of tours.
  • The method provides a direct equivalence between the Bellman-Held-Karp dynamic programming algorithm and convex optimization over GCS.
  • A branch-and-bound heuristic using minimum 1-trees extends exact solutions to larger problems with optimality certificates.
  • Alternative lower bounds can be computed to assess and certify the quality of obtained solutions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The augmentation technique may generalize to other combinatorial routing problems such as vehicle routing with convex regions.
  • Hybrid algorithms could combine the GCS shortest-path method with traditional dynamic programming for better scaling on mixed instances.
  • In robotics, this could enable exact trajectory planning for agents required to visit multiple convex regions without repetition.

Load-bearing premise

The TSP visiting constraints can be encoded into the augmented GCS structure without introducing approximation or losing exact equivalence to the original combinatorial problem.

What would settle it

A small TSP instance where the shortest path computed in the augmented GCS produces a tour that visits some set more than once or skips a required set.

Figures

Figures reproduced from arXiv: 2604.06406 by Gael Luna, Tyler Summers.

Figure 1
Figure 1. Figure 1: (Left) Complete graph on 7 target sets. (Middle) Augm [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: AGCS-TSPS of a graph with five target sets and initial [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: (Left) Optimal bounded cost, (Right) Optimal realiz [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of four heuristics for a 100 vertex graph: [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: (Top) Example tour, (Middle) candidate tour, (Bot [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
read the original abstract

We present a trajectory optimization algorithm for the traveling salesman problem (TSP) in graphs of convex sets (GCS). Our framework uses an augmented graph of convex sets to encode the TSP specification and solve it exactly as a shortest path problem in GCS. We establish a precise relationship between the landmark Bellman-Held-Karp algorithm and the augmented graph of convex sets with a TSP specification. Additionally, we present a branch and bound heuristic that uses minimum 1-trees to obtain certifiably optimal or near optimal solutions and scales to problems far larger than the exact framework can handle. To assess and certify performance, we explore several alternative lower bounds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The manuscript proposes an augmented graph of convex sets (GCS) framework to solve the traveling salesman problem (TSP) exactly by reducing it to a shortest path problem in GCS. It establishes an equivalence to the Bellman-Held-Karp dynamic programming algorithm via subset-state augmentation that replicates the DP recurrence. The authors also introduce a branch-and-bound heuristic using minimum 1-trees for certifiably optimal or near-optimal solutions on larger instances and explore alternative lower bounds for assessment and certification.

Significance. If the claimed exact equivalence holds, the work provides a rigorous bridge between GCS-based convex optimization and classical combinatorial TSP methods, enabling exact solutions without relaxation while extending scalability through the heuristic. The precise relationship to Bellman-Held-Karp and use of certifiable bounds are notable strengths for applications in trajectory optimization and systems control.

minor comments (4)
  1. §2 (Preliminaries on GCS): The definition of the augmented graph structure and how subset states are incorporated into the convex sets should include an explicit diagram or pseudocode to clarify the encoding of visiting constraints.
  2. Abstract and §1: The phrase 'trajectory optimization algorithm' is somewhat misleading for a purely combinatorial TSP formulation; consider rephrasing to emphasize the reduction to shortest-path in GCS.
  3. §5 (Lower bounds): The alternative lower bounds are mentioned but lack a direct comparison table to the 1-tree bound or the exact GCS method; adding quantitative results would strengthen the certification claims.
  4. Related work: The manuscript should cite the foundational GCS paper (e.g., the original GCS formulation) and recent TSP solvers in the GCS literature for better context.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, recognition of the equivalence to the Bellman-Held-Karp algorithm, and the strengths noted in the branch-and-bound heuristic with minimum 1-trees. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper reformulates TSP as a shortest-path problem in an augmented GCS by encoding visiting constraints via subset states, then explicitly establishes equivalence to the Bellman-Held-Karp dynamic program through replication of its recurrence. This equivalence is a direct structural correspondence between the two formulations rather than a reduction of any claimed result to fitted parameters, self-definitions, or unverified self-citations. Prior GCS literature is referenced as background but does not bear the load of the central TSP encoding or exactness claim, which remains independently verifiable against the standard DP. No ansatz smuggling, renaming of known results, or uniqueness theorems imported from the authors' prior work appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract, no explicit free parameters, axioms, or invented entities are described; the method presumably relies on standard assumptions of convex optimization and graph shortest-path algorithms.

pith-pipeline@v0.9.0 · 5393 in / 1090 out tokens · 39589 ms · 2026-05-10T18:43:56.605827+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    S. M. LaV alle, Planning algorithms . Cambridge University Press, 2006

    work page 2006

  2. [2]

    The traveling salesman problem: An overvie w of exact and approximate algorithms,

    G. Laporte, “The traveling salesman problem: An overvie w of exact and approximate algorithms,” European Journal of Operational Re- search, 1992

    work page 1992

  3. [3]

    Dynamic programming treatment of the trave lling sales- man problem,

    R. Bellman, “Dynamic programming treatment of the trave lling sales- man problem,” Journal of the ACM , 1962

    work page 1962

  4. [4]

    A dynamic programming approach to sequencing problems,

    M. Held and R. M. Karp, “A dynamic programming approach to sequencing problems,” Journal of the Society for Industrial and Applied mathematics , 1962

    work page 1962

  5. [5]

    Shortest paths in graphs of convex sets,

    T. Marcucci, J. Umenberger, P . Parrilo, and R. Tedrake, “ Shortest paths in graphs of convex sets,” SIAM Journal on Optimization , 2024

    work page 2024

  6. [6]

    A unified and scalable method for optimizat ion over graphs of convex sets,

    T. Marcucci, “A unified and scalable method for optimizat ion over graphs of convex sets,” 2025

    work page 2025

  7. [7]

    Motion planning around obstacles with convex optimization,

    T. Marcucci, M. Petersen, D. von Wrangel, and R. Tedrake, “Motion planning around obstacles with convex optimization,” Science robotics, 2023

    work page 2023

  8. [8]

    Motion planning with precedence specification s via augmented graphs of convex sets,

    S. Y ou, G. Luna, J. Shaikh, D. Gostin, Y . Xiang, J. Koeln, a nd T. Summers, “Motion planning with precedence specification s via augmented graphs of convex sets,” Oct. 2025

    work page 2025

  9. [9]

    An effective implementation of the lin-ke rnighan trav- eling salesman heuristic,

    K. Helsgaun, “An effective implementation of the lin-ke rnighan trav- eling salesman heuristic,” European Journal of Operational Research , Oct. 2000

    work page 2000

  10. [10]

    V ariants of travelling s alesman prob- lem: A survey,

    K. Ilavarasi and K. S. Joseph, “V ariants of travelling s alesman prob- lem: A survey,” in International Conference on Information Commu- nication and Embedded Systems (ICICES2014) . IEEE, 2014, pp. 1–7

    work page 2014

  11. [11]

    A mixed -integer conic program for the moving-target traveling salesman pro blem based on a graph of convex sets,

    A. G. Philip, Z. Ren, S. Rathinam, and H. Choset, “A mixed -integer conic program for the moving-target traveling salesman pro blem based on a graph of convex sets,” in 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) , 2024, pp. 8847–8853

    work page 2024

  12. [12]

    A complete algorithm for a moving target traveling salesma n problem with obstacles,

    A. Bhat, G. Gutow, B. Vundurthy, Z. Ren, S. Rathinam, and H. Choset, “A complete algorithm for a moving target traveling salesma n problem with obstacles,” 2024

    work page 2024

  13. [13]

    A complete and bounded-suboptimal algorithm for a moving target traveling salesman problem with obstacles in 3d*,

    ——, “A complete and bounded-suboptimal algorithm for a moving target traveling salesman problem with obstacles in 3d*,” i n 2025 IEEE International Conference on Robotics and Automation (ICRA ). IEEE, 2025, pp. 6132–6138

    work page 2025

  14. [14]

    Monitoring temporal propert ies of con- tinuous signals,

    O. Maler and D. Nickovic, “Monitoring temporal propert ies of con- tinuous signals,” in International symposium on formal techniques in real-time and fault-tolerant systems . Springer, 2004

    work page 2004

  15. [15]

    Baier and J.-P

    C. Baier and J.-P . Katoen, Principles of model checking . MIT press, 2008

    work page 2008

  16. [16]

    Solution of a large- scale traveling-salesman problem,

    G. Dantzig, R. Fulkerson, and S. Johnson, “Solution of a large- scale traveling-salesman problem,” Journal of the Operations Research Society of America , 1954

    work page 1954

  17. [17]

    The traveling-salesman problem and minimum spanning trees,

    M. Held and R. M. Karp, “The traveling-salesman problem and minimum spanning trees,” Operations Research, 1970

    work page 1970

  18. [18]

    The traveling-salesman problem and minimum spann ing trees: Part ii,

    ——, “The traveling-salesman problem and minimum spann ing trees: Part ii,” Mathematical Programming, 1971

    work page 1971

  19. [19]

    B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms. Springer, 2012

    work page 2012

  20. [20]

    On the shortest spanning subtree of a gra ph and the traveling salesman problem,

    J. B. Kruskal, “On the shortest spanning subtree of a gra ph and the traveling salesman problem,” Proceedings of the American Mathemat- ical Society , 1956

    work page 1956

  21. [21]

    A method for solving traveling-salesman p roblems,

    G. A. Croes, “A method for solving traveling-salesman p roblems,” Operations Research, 1958

    work page 1958

  22. [22]

    CVXPY: A Python-embedded model ing language for convex optimization,

    S. Diamond and S. Boyd, “CVXPY: A Python-embedded model ing language for convex optimization,” Journal of Machine Learning Research, vol. 17, no. 83, pp. 1–5, 2016

    work page 2016

  23. [23]

    A r ewriting system for convex optimization problems,

    A. Agrawal, R. V erschueren, S. Diamond, and S. Boyd, “A r ewriting system for convex optimization problems,” Journal of Control and Decision, vol. 5, no. 1, pp. 42–60, 2018

    work page 2018

  24. [24]

    Gurobi Optimizer Referenc e Manual,

    Gurobi Optimization, LLC, “Gurobi Optimizer Referenc e Manual,”

    work page

  25. [25]

    Available: https://www.gurobi.com

    [Online]. Available: https://www.gurobi.com

    work page