cs.AIAug 21, 2026

Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets

Authors: Jingtao Tang, Hang Ma

Organizations: School of Computing Science, Simon Fraser University, Burnaby, BC V5A1S6, Canada

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We formalize the Steiner Traveling Salesman Problem (Steiner-TSP) on Graphs of Convex Sets (GCS), which seeks a minimum-cost closed trajectory through required convex sets while allowing optional transit vertices and revisits. To explore the resulting infinite solution space, we propose a unified branch-and-bound search over rooted walk prefixes. Additive lower-bound-graph costs bound committed prefixes, while a cut-separated connected-flow relaxation lower-bounds the residual cost of visiting every remaining target and returning to the root. Under a uniform positive-cost assumption, best-first traversal terminates after finitely many expansions on every feasible instance without an initial incumbent, whereas depth-first traversal does so once a finite incumbent is available. For a user-specified factor ε≥1ε\geq1, a global lower bound certifies that either strategy's incumbent cost is at most εε times the global optimum. We further demonstrate joint sensing-mode, visitation-order, and continuous-trajectory selection for a mobile-manipulator inspection task, including action precedences expressed in linear temporal logic over finite traces (LTLf_f). Both traversal strategies find feasible solutions on all benchmark instances within 30s with mean certified optimality gaps of 28.1% and 29.7%, respectively, whereas two recent baselines succeed on only about half of the instances

Figures & tables

Figure 1: Steiner-TSP on a GCS seeks a minimum-cost closed trajectory from root rr (red) visiting all target convex sets (yellow). Black dashed arrows denote directed GCS edges (solid if used). The orange solution (a) is feasible without revisits, whereas the blue solution (b) exploits vertex revisits and is globally optimal, with circled numbers identifying the underlying GCS edges.
Figure 2: Steiner-TSP on GCS solution trajectories (blue) in rand with a 2-D GCS of gray polygons, maze with a 3-D GCS exactly partitioning the free voxels outside black walls, and iiwa with a 7-D GCS comprising IRIS-NP [ 25 ] regions seeded by representative collision-free configurations.
Domain∣V∣|V|∣E∣|E|Degree∣Vt∣|V_{t}|ddLBG
rand8/23.6/4120/60.6/1041/2.51/78/23.6/4120.07s
maze63/63/63124/125.2/1301/1.99/410/30/5030.14s
iiwa18/24/30104/116.0/1281/4.93/133/9/1574.57s
Table I: Steiner-TSP on GCS instance complexity. The ∣V∣|V| , ∣E∣|E| , Degree, and ∣Vt∣|V_{t}| columns report the minimum/mean/maximum. The dd column reports the configuration-space dimension, and LBG column reports the mean precomputation time in seconds.
 SolverCostGap ↓\downarrowFeasible ↑\uparrowNPI ↓\downarrowClosedEval.
 Regret ↓\downarrowNodesWalks
randGHOST [ 13 ]2.1%50.4%43/600.386–294
MICP [ 1 ]24.5%100.0%38/600.603––
Ours (BF)0.0%18.3%60/600.0118.6k666
Ours (DF)1.8%21.7%60/600.0231.2k429
Alt-G28.0%33.0%60/600.2057361
Table II: Ablation and performance comparison results.
Figure 3: Mobile-manipulator inspection: (a) PRM-based generalized-TSP baseline, (b) Ours (BF), and (c) Ours (BF) with LTL f [ 27 ] action precedences. Translucent arm poses encode normalized active-motion progress from blue (early) to orange (late), as shown by the right color bar. Red circled A–H mark tasks; black circled 1–8 show execution order and simulation timestamps.
More in this topic

Traveling Salesperson Problem

The Traveling Salesperson Problem studies algorithms for finding shortest tours that visit every city exactly once.

See all 38 papers

Explore similar work

CardsList
Jun 17, 2026

Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles

The Moving-Target Traveling Salesman Problem (MT-TSP) seeks a minimum cost trajectory for an agent that departs from a static depot, visits a set of moving targets, each within one of their assigned time windows, and returns to the depot. In this article, we study the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO), a generalization of the MT-TSP where the agent trajectory must avoid moving obstacles. We present a Mixed-Integer Conic Programming (MICP) formulation that can be solved using off-the-shelf solvers, as well as a fast and scalable Two-Phase Bilevel Search (TPBS) algorithm that computes high-quality feasible solutions for the problem. We evaluate our approaches against an existing baseline algorithm on a broad range of problem instances with up to 40 targets and 40 obstacles. The results demonstrate that both the proposed methods significantly outperform the baseline with respect to success rates, solution costs, and computation time.

Allen George Philip, Anoop Bhat, Sivakumar Rathinam +1

Mechanical Engineering, Texas A&M University, College Station, TX 77843-3123 · Robotics Institute, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213, USA · Mechanical Engineering, and Computer Science and Engineering, Texas A&M University, College Station, TX 77843-3123

Traveling Salesperson ProblemCombinatorial OptimizationConstrained OptimizationDynamic Obstacle AvoidanceRobot Motion Planning
AskPDF
Jul 13, 2026

Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems

Learning-based methods for the traveling salesman problem (TSP) are often evaluated through the tours produced after decoding or search, but the learned object itself frequently lives in a surrogate space such as heatmaps, assignments, construction policies, or search-guidance scores. This hides the fundamental question: what Hamiltonian structure has actually been learned before decoding? In this study, we directly answer this question by learning TSP through a structurally meaningful latent object, rather than leaving most of the Hamiltonian structure to the final decoding stage. Based on a connected-by-construction rooted 11-tree Gibbs family, we propose an end-to-end unsupervised learning pipeline called C2TSP. The pipeline learns residual edge perturbations from unbiased TSP cost through implicit differentiation. For structural correction, a smoothed Held--Karp layer restores expected degree balance, while certificate-guided sharpening further pushes the connected distribution toward more tour-like structures. Experiments show that C2TSP yields strong decoding performance while preserving interpretable structural information. Ablations further verify that edge perturbation and certificate-guided sharpening jointly improve both tour cost and tour-like structure.

Ke Sun, Xinyuan Zhang, Xinwu Qian

Department of Civil and Environmental Engineering, Rice University, Houston, TX

Traveling Salesperson ProblemCombinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Jul 21, 2026

Graph Neural Network-based Algorithm Selection for the Traveling Salesman Problem: A Systematic Study of Cost and Rank Losses under Distinct Budget Regimes

Automated Algorithm Selection (AS) aims to improve problem-solving performance by selecting, for each problem instance, the most suitable algorithm from a predefined portfolio. This is particularly relevant to the Traveling Salesman Problem (TSP), where solver performance is strongly instance-dependent. We introduce GNNAS-TSP, a Graph Neural Network (GNN)-based AS framework that learns TSP instance representations directly from raw graph data, avoiding manual feature engineering. GNNAS-TSP formulates AS as a joint cost-prediction and ranking task. We evaluate cost-based (mean squared error (MSE), mean absolute error (MAE), and Huber), rank-based (RankNet, ListNet, and LambdaRank), and hybrid learning objectives for a portfolio comprising Chained Lin-Kernighan, Edge Assembly Crossover, Lin-Kernighan-Helsgaun, Multiagent Optimization System, and Concorde. Experiments use fixed computational budgets of 10 and 60 seconds. On the held-out test set, the selected configurations improve on the Single Best Solver (SBS) in normalized solution cost at both budgets. For the 10s budget, AS achieves substantial and statistically significant cost improvement over SBS. Overall, the results suggest that GNNAS-TSP is a useful meta-solving strategy when exploitable variation exists across solver performance.

Zhaoxuan Li, Jiale Yang, Yifei Lu +1

Duke Kunshan University, 8 Duke Avenue, Kunshan, 215316, China

Traveling Salesperson ProblemAlgorithm SelectionLearning to RankCombinatorial Optimization
AskPDF