Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets
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 $ε\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 (LTL$_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
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search
Graph neural networks are useful for learning problems, as well as for combinatorial and graph problems such as the Subgraph Isomorphism Problem and the Traveling Salesman Problem. We describe an approach for computing S…
Graph Neural NetworkTraveling Salesman ProblemSteiner Traveling Salesman Problem with Quantum Annealing
The Steiner Traveling Salesman Problem (STSP) is a variant of the classical Traveling Salesman Problem. The STSP involves incorporating steiner nodes, which are extra nodes not originally part of the required visit set b…
Traveling Salesman ProblemComputing Steiner Trees using Graph Neural Networks
Graph neural networks have been successful in many learning problems and real-world applications. A recent line of research explores the power of graph neural networks to solve combinatorial and graph algorithmic problem…
Graph AttentionGraph GenerationGraph LearningSteiner Tree Problem+1Towards Solving the Gilbert-Pollak Conjecture via Large Language Models
The Gilbert-Pollak Conjecture \citep{gilbert1968steiner}, also known as the Steiner Ratio Conjecture, states that for any finite point set in the Euclidean plane, the Steiner minimum tree has length at least $\sqrt{3}/2 …
Submarine Cable Network Design for Regional Connectivity
This paper optimizes path planning for a trunkand-branch topology network in an irregular 2-dimensional manifold embedded in 3-dimensional Euclidean space with application to submarine cable network planning. We go beyon…
Steiner Tree Problem