Shortest Paths in Graphs of Convex Sets
DOI10.1137/22m1523790arXiv2101.11565OpenAlexW3123076862WikidataQ128905454 ScholiaQ128905454MaRDI QIDQ6188512
Russ Tedrake, Tobia Marcucci, Jack Umenberger, Pablo A. Parrilo
Publication date: 7 February 2024
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2101.11565
optimal controlshortest-path problemperspective formulationgraph problems with neighborhoodsmixed-Integer convex programming
Programming involving graphs or networks (90C35) Convex programming (90C25) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Control/observation systems involving computers (process control, etc.) (93C83) Discrete-time control/observation systems (93C55) Paths and cycles (05C38) Distance in graphs (05C12)
Cites Work
- Unnamed Item
- Integer programming formulations for the elementary shortest path problem
- Generalized network design problems. Modeling and optimization.
- Relaxations and discretizations for the pooling problem
- A perspective-based convex relaxation for switched-affine optimal control
- Control of systems integrating logic, dynamics, and constraints
- Approximation algorithms for the Geometric Covering Salesman Problem
- Semidefinite programming relaxations for semialgebraic problems
- Generalized Steiner problems and other variants
- Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods
- Generalized network design problems.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A branch-and-cut method for 0-1 mixed convex programming
- Convex programming for disjunctive convex optimization
- New SOCP relaxation and branching rule for bipartite bilinear programs
- The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
- Perspective cuts for a class of convex 0-1 mixed integer programs
- Perspective reformulations of mixed integer nonlinear programs with indicator variables
- The bipartite Boolean quadric polytope
- Global Optimization with Polynomials and the Problem of Moments
- Euclidean Shortest Paths
- Integer Programming
- Rectilinear Shortest Path and Rectilinear Minimum Spanning Tree with Neighborhoods
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Touring a sequence of polygons
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- The shortest path with at most / nodes in each of the series/parallel clusters
- The travelling salesman problem with neighbourhoods: MINLP solution
- Reducibility among Combinatorial Problems
- Warm Start of Mixed-Integer Programs for Model Predictive Control of Hybrid Systems
- Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
- Mixed-integer formulations for optimal control of piecewise-affine systems
- Simultaneous Convexification of Bilinear Functions over Polytopes with Application to Network Interdiction
- Minimum Spanning Tree with Neighborhoods
- Convex Analysis
- Equivalence of hybrid dynamical models
