graph problems with neighborhoodsmixed-Integer convex programmingoptimal controlperspective formulationshortest-path problem
Distance in graphs (05C12) Paths and cycles (05C38) Mixed integer programming (90C11) Convex programming (90C25) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Discrete-time control/observation systems (93C55) Control/observation systems involving computers (process control, etc.) (93C83)
Abstract: Given a graph, the shortest-path problem requires finding a sequence of edges with minimum cumulative length that connects a source vertex to a target vertex. We consider a variant of this classical problem in which the position of each vertex in the graph is a continuous decision variable constrained in a convex set, and the length of an edge is a convex function of the position of its endpoints. Problems of this form arise naturally in many areas, from motion planning of autonomous vehicles to optimal control of hybrid systems. The price for such a wide applicability is the complexity of this problem, which is easily seen to be NP-hard. Our main contribution is a strong and lightweight mixed-integer convex formulation based on perspective operators, that makes it possible to efficiently find globally optimal paths in large graphs and in high-dimensional spaces.
Recommendations
- Bounded-curvature shortest paths through a sequence of points using convex optimization
- scientific article; zbMATH DE number 1182917
- Continuous-time shortest path problems with stopping and starting costs
- Continuous-Time Shortest Path Problems and Linear Programming
- Shortest paths in the plane with convex polygonal obstacles
Cites work
- A branch-and-cut method for 0-1 mixed convex programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A perspective-based convex relaxation for switched-affine optimal control
- Approximation algorithms for the Geometric Covering Salesman Problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Control of systems integrating logic, dynamics, and constraints
- Convex Analysis
- Convex programming for disjunctive convex optimization
- Equivalence of hybrid dynamical models
- Euclidean shortest paths. Exact or approximate algorithms.
- Generalized network design problems.
- Generalized network design problems. Modeling and optimization.
- Generalized Steiner problems and other variants
- Global optimization with polynomials and the problem of moments
- Integer Programming
- Integer programming formulations for the elementary shortest path problem
- Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
- Minimum Spanning Tree with Neighborhoods
- Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods
- Mixed-integer formulations for optimal control of piecewise-affine systems
- Network flows. Theory, algorithms, and applications.
- New SOCP relaxation and branching rule for bipartite bilinear programs
- Perspective cuts for a class of convex 0-1 mixed integer programs
- Perspective reformulations of mixed integer nonlinear programs with indicator variables
- Rectilinear shortest path and rectilinear minimum spanning tree with neighborhoods
- Reducibility among combinatorial problems
- Relaxations and discretizations for the pooling problem
- Semidefinite programming relaxations for semialgebraic problems
- Simultaneous convexification of bilinear functions over polytopes with application to network interdiction
- The bipartite Boolean quadric polytope
- The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
- The shortest path with at most / nodes in each of the series/parallel clusters
- The travelling salesman problem with neighbourhoods: MINLP solution
- Touring a sequence of polygons
- Warm Start of Mixed-Integer Programs for Model Predictive Control of Hybrid Systems
Cited in
(1)
This page was built for publication: Shortest Paths in Graphs of Convex Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6188512)
