PaperlayerView exact revision on arXiv

Source-linked AI summary

Shortest Paths in Graphs of Convex Sets

Tobia Marcucci, Jack Umenberger, Pablo A. Parrilo, Russ Tedrake

arXiv:2101.11565v5cs.DMmath.OC

TL;DR

The paper studies shortest paths where vertex positions vary continuously within convex sets and edge lengths are convex functions of endpoint positions, a flexible but NP-hard formulation. It develops a compact mixed-integer convex formulation with perspective-based relaxations, recovering globally optimal paths and supporting large graphs, high-dimensional spaces, and hybrid-system control. Experiments report typically tight relaxations, fast global optimization, and control solutions outperforming state-of-the-art techniques, while noting that random-instance representativeness and relaxation tightness can have important limits.

  • Problem

    The paper addresses the NP-hard shortest-path problem in graphs where vertex positions lie in convex sets and edge lengths depend convexly on endpoint positions.

  • Method

    It formulates the problem as a compact mixed-integer convex program using perspective-based, set-based relaxations of bilinear constraints.

  • Results

    Experiments show typically tight relaxations, rapid solution of large problems to global optimality, and control performance that outperforms state-of-the-art techniques.

  • Takeaways & Limitations

    The framework provides a versatile approach for shortest-path and hybrid-control problems in large graphs and high-dimensional spaces.

  • Takeaways & Limitations

    The random instances are not completely representative, and a contrived example shows that the relaxation can be arbitrarily loose.

Abstract

from arXiv · show

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.

1. Introduction.

The paper introduces shortest paths in graphs of convex sets as a versatile framework for applications including drone scheduling and hybrid-system control. Its main contribution is a compact, strong mixed-integer convex formulation using perspective-based relaxations, with computational evidence of scalability and faster control optimization.

  • 1. Introduction.: The SPP in GCS generalizes shortest paths by allowing vertex positions to vary within convex sets and supports diverse practical applications.The framework is motivated by drone flight scheduling, recharging regions, and optimal control of discrete-time hybrid systems.
  • 1.1. Contributions.: The proposed MICP uses a natural extension of network-flow modeling to solve NP-hard instances in large graphs and high-dimensional spaces.The formulation is described as lightweight and applicable to graphs with hundreds of vertices and spaces with tens of dimensions.
  • 1.1. Contributions.: A set-based perspective relaxation handles bilinear constraints directly from abstract convex-set representations, including sets accessible only through separation oracles.This design avoids dependence on explicit descriptions of the sets defining the graph.
  • 1.1. Contributions.: Control experiments report that transition-based binary variables produce slightly larger but much stronger MICPs that are orders of magnitude faster than state-of-the-art techniques.The formulation selects transitions between modes rather than encoding the mode at each time step.
  • 1.2. Related graph problems.: The framework differs from related neighborhood and obstacle-routing problems because its sets are convex and the visiting order is not predefined.Existing neighborhood formulations may rely on disjoint rectilinear polygons, L1 penalties, or fixed visitation orders.

Euclidean shortest paths.

The paper formalizes a graph whose vertices contain points in compact convex sets and whose edge lengths depend on endpoint locations.

  • Euclidean shortest paths.: Each graph vertex v has a nonempty compact convex set X_v in R^n containing a point x_v.

2. Problem statement.

The SPP in GCS jointly chooses an s-t path and continuous positions for visited vertices, minimizing the sum of convex endpoint-dependent edge lengths. Infinite edge costs can encode convex coupling constraints, including dynamics, but the joint problem is NP-hard.

  • 2. Problem statement.: Edge lengths are proper, closed, convex functions of the endpoint positions and need not satisfy metric symmetry or the triangle inequality.
  • 2. Problem statement.: The decision variables are the discrete path and continuous vertex positions, while the objective minimizes total path length over visited vertices.Positions of vertices outside the selected path are irrelevant.
  • 2. Problem statement.: Using Euclidean distance makes shortest-path polylines as straight as possible, whereas squared Euclidean distance can make straight trajectories suboptimal when they require long steps.
  • 2. Problem statement.: Assigning infinite edge length outside a convex set enforces endpoint coupling constraints, which can represent system dynamics in optimal-control models.
  • 2. Problem statement.: Fixing positions yields the classical shortest-path problem, and fixing the path yields a convex program, but optimizing both simultaneously is NP-hard.

3. Complexity analysis.

The SPP in GCS is NP-hard even with one-dimensional convex sets, and remains NP-hard under acyclicity, disjoint sets, and positively homogeneous edge lengths. The hardness reduction encodes Hamiltonian-path structure through squared-distance costs.

  • 3. Complexity analysis.: The SPP in GCS is NP-hard by a polynomial reduction from the Hamiltonian-Path Problem.
  • 3. Complexity analysis.: The reduction uses singleton source and target sets, interval sets for all other vertices, and squared Euclidean edge lengths.
  • 3. Complexity analysis.: For a path with K edges, the reduction gives optimal cost 1/K, so minimizing cost favors paths with the maximum number of edges and identifies Hamiltonian paths.
  • 3. Complexity analysis.: Hardness persists even when all convex sets are one-dimensional intervals, motivating analysis of additional structural assumptions.
  • 3. Complexity analysis.: The problem remains NP-hard when the graph is acyclic, the sets are disjoint, and edge lengths are positively homogeneous.

4. Convex-analysis background.

The section introduces perspective operators for convex sets and functions, showing how they preserve convexity and support conic optimization and duality arguments used later in the formulation.

  • Perspective maps a set in n dimensions to a closed convex cone in n+1 dimensions through homogenization.For unbounded sets, closure adds limit points with λ = 0.
  • A conic representation X = {x : Ax + b ∈ K} yields the perspective set {(x, λ) : λ ≥ 0, Ax + bλ ∈ K}.This preserves linear, second-order-cone, and semidefinite representability for common set classes.
  • The perspective of a closed convex function is defined through the perspective of its epigraph and is jointly convex in x and λ.For λ > 0, it equals λf(x/λ); for λ < 0 it is infinite, while proper functions satisfy ˜f(0, 0) = 0.
  • Perspective functions remain numerically tractable because conic epigraph representations can be transformed and minimized with standard solvers.A slack variable can represent the resulting epigraph constraint.
  • The perspective of a function restricted to a convex set combines the perspective function with the perspective set, while set inequalities lift through perspective functions.These constructions provide direct formulations for constrained convex functions and convex sets.
  • The cone of valid inequalities contains all affine inequalities valid over a set and is closed and convex even when the set is not.It is closely related to, but distinct from, the polar set.
  • For a closed convex set, its perspective cone and cone of valid inequalities are dual cones.The relationship follows by representing the perspective cone through all valid inequalities and applying the bipolar theorem.
  • These perspective and duality tools are used to construct the paper’s strong mixed-integer convex formulation from a network-flow model and a convex relaxation.The formulation first introduces bilinear constraints and then replaces them with a tailored convex relaxation.

5. Mixed-integer convex formulation.

The formulation extends network flow to graphs of convex sets, uses perspective functions to handle edge costs, and convexifies bilinear coupling constraints into a compact MICP equivalent to the original problem.

  • 5.1. Network-flow formulation of the SPP.: The classical network-flow model uses nonnegative edge flows to encode a source-to-target path, with flow balance and at-most-one traversal at intermediate vertices.Although flows are not explicitly binary, every basic feasible solution is binary; the degree constraint is retained because it matters in the final MICP.
  • 5.1. Network-flow formulation of the SPP.: Jointly optimizing vertex positions and path selection produces a biconvex problem whose only nonconvexity is in products between positions and flow variables.Fixing either positions or the path reduces the problem to a convex optimization problem.
  • 5.2. Biconvex formulation.: Perspective edge-cost functions make inactive edges contribute zero even when their original edge length is infinite.Auxiliary variables match endpoint positions when flow is one and collapse to zero when flow is zero.
  • 5.2. Biconvex formulation.: The biconvex formulation can be represented with flows, vertex positions, and auxiliary endpoint variables, and an optimal local solution admits binary flows without changing cost.Fixing vertex positions reduces the problem to the network-flow LP, whose optimal basic flows are binary.
  • 5.2. Biconvex formulation.: The biconvex model is numerically challenging because its bilinear equality constraints make local optimization difficult.This motivates replacing those constraints with convex envelopes.
  • 5.3. Convex relaxation of the bilinear constraints.: Valid flow inequalities are lifted into convex constraints by multiplying them with vertex-membership relations, producing perspective-cone envelopes.The resulting constraints are applied to the flow constraints and nonnegativity conditions to build the MICP.
  • 5.4. Degree constraints.: The formulation uses O(|E|) binary variables, O(n|E|) continuous variables, and O(n(|V| + |E|)) constraints under the stated cone-size assumption.Its design balances relaxation tightness against program size and supports standard branch-and-bound global optimization.
  • 5.3. Convex relaxation of the bilinear constraints.: The MICP has the same optimal value as the SPP in GCS and recovers an optimal path from edges whose flow variables equal one.Vertex positions are reconstructed from the MICP solution for the source, target, and intermediate vertices.

6. Alternative formulations.

The paper compares its compact MICP with weaker McCormick relaxations and stronger but more expensive alternatives, positioning it as a practical compromise.

  • Independent McCormick envelopes can produce a more compact MICP, but their convex relaxation is loose and solution times are generally much larger.This comparison uses bounding boxes around the convex vertex sets.
  • Stronger alternatives include subtour-elimination constraints, vertex-wise convex-hull formulations, and semidefinite relaxations, but they may be more expensive.The authors report that their MICP had lower solution times than the other formulations tested and was the best compromise in their computational experience.

7. Analysis of the mixed-integer formulation.

The analysis develops a set-based convex relaxation for bilinear constraints and uses it to justify a strong, compact mixed-integer formulation for shortest paths in graphs of convex sets.

  • 7.1. Set-based relaxation of bilinear constraints.: The relaxation multiplies valid inequalities of X and Y, linearizes their products with Z = xy^⊤, and obtains an infinite family of valid linear inequalities.The original bilinear set is S = {(x, y, Z): x ∈ X, y ∈ Y, Z = xy^⊤}.
  • 7.1. Set-based relaxation of bilinear constraints.: When Y is a polytope, the infinite relaxation can be represented finitely with perspective-cone constraints, yielding an efficient asymmetric formulation when Y has few facets.The asymmetric form works directly with abstract set representations rather than explicit constraints defining X.
  • 7.1. Set-based relaxation of bilinear constraints.: In the SPP formulation, vertex flow polytopes and auxiliary matrices instantiate the generic relaxation by replacing each bilinear constraint set S_v with its relaxed counterpart S′_v.The construction organizes incident flows into y_v and auxiliary variables into Z_v, with Z_v = x_v y_v^⊤ in the original formulation.
  • 7.2. Tightness of the relaxation S′.: The relaxation need not equal conv S in general: it is exact for interval sets but can be strictly weaker for multidimensional boxes, where it reduces to first-level RLT.For polytopic sets, the convex-hull formulation can instead scale with extreme points, whereas the proposed relaxation scales with facets.
  • 7.2. Tightness of the relaxation S′.: Despite that limitation, the proposed MICPs typically offer a better strength-size tradeoff and are much faster to solve in the authors’ experience.This practical comparison motivates using the compact relaxation instead of a potentially larger convex-hull description.
  • 7.3. Geometric proof of Theorem 5.7.: The relaxation is exact when Y is evaluated at an extreme point, so path-induced extreme flows establish validity of the mixed-integer formulation.The geometric proof uses active linearly independent inequalities at an extreme point to recover Z = xŷ^⊤.
  • 7.3. Geometric proof of Theorem 5.7.: The analysis connects the relaxation to classical McCormick, RLT, and Lovász–Schrijver techniques while exploiting bilinear structure to avoid semidefinite constraints and redundant variables.The resulting relaxation is described as smaller and as tight as the first Lovász–Schrijver level, while higher-level or semidefinite alternatives are slower in practice.
  • 7.4. Related relaxation techniques.: The framework also supports optimal-control models by representing discrete-time transitions as graph edges and state-control pairs as convex-set vertex variables.This extends the formulation beyond shortest paths to control problems involving discrete decisions.

8. Control applications.

The paper casts minimum-time linear and piecewise-affine control problems as shortest paths in graphs of convex sets. The constructions encode dynamics through edge feasibility and recover optimal trajectories from the resulting path.

  • 8.1. Minimum-time control.: Minimum-time linear control uses an ordered graph with shortcut-to-target edges, where each vertex stores a state-control pair constrained in a compact convex set.The source fixes the initial state, the target is the origin, and edge length 1 represents a dynamically feasible transition.
  • 8.1. Minimum-time control.: The MICP solution identifies a path whose edge count equals the optimal time horizon, while its selected vertex variables recover the control sequence and state trajectory.The terminal state is retrieved as s_T = s_t = 0.
  • 8.2. Control of hybrid systems.: Piecewise-affine hybrid control is represented with layered graphs whose vertices correspond to discrete modes and whose interlayer edges enforce mode-specific dynamics.The source connects to the first layer, consecutive layers are fully connected, and the final layer connects to the target.
  • 8.2. Control of hybrid systems.: Convex terminal constraints and penalties can be incorporated by modifying the target set and the lengths of edges entering the target.This extends the basic construction beyond a fixed terminal origin.
  • 8.2. Control of hybrid systems.: The control-oriented GCS has size linear in the time horizon but quadratic in the number of discrete modes, trading larger formulations for stronger MICPs.The paper notes that this strength can justify the size increase relative to formulations linear in both quantities.

9. Numerical results.

Numerical experiments show that the proposed MICP is typically tight and scales to large graphs, high-dimensional spaces, and an optimal-control application, while relaxation quality depends on edge length, dimension, density, and graph symmetry.

  • 9.1. Two-dimensional example.: For Euclidean edge length in the two-dimensional example, the proposed relaxation is exact for every set-size scale σ, while the McCormick relaxation becomes trivial for larger sets.For squared Euclidean length, the proposed relaxation remains tight as σ approaches zero and recovers the bound 11.6 for large σ, whereas McCormick gives zero.
  • 9.2. Large-scale random instances.: The relaxation is tight in almost all random Euclidean-length instances, whereas squared-Euclidean instances become harder as dimension and graph density increase.In nominal squared-length instances, the maximum relaxation gap and runtime are 2.1% and 0.66s.
  • 9.2. Large-scale random instances.: For squared Euclidean length, increasing dimension to n = 20 or edges to 500 raises maximum gaps to 28.9% and 32.9%, while a sparser 250-vertex graph reduces them to 5.3%.The corresponding worst-case runtimes are 72s, 174s, and 5.4s, respectively.
  • 9.2. Large-scale random instances.: The proposed formulation outperforms the McCormick formulation, whose nominal median runtimes are 12.9 and 10.3 times larger and whose relaxation gaps are 29% and 34%.For Euclidean and squared-Euclidean edge lengths respectively, McCormick maximum runtimes are 4.3 and 2.7 times larger, with maximum gaps of 52% and 58%.
  • 9.3. Optimal control.: The control optimum follows a winding trajectory with cost 9.37 because low-controllability regions make geometrically direct shortcuts too expensive.The relaxation's reconstructed trajectory more closely resembles the MICP solution and identifies low-controllability regions as high-cost.
  • 9.3. Optimal control.: In the control problem, the proposed relaxation has value 7.46, 80% of the MICP value, versus 0.67, or 7%, for the alternative relaxation.The proposed relaxation has a 20% gap and reduces solution time to 7.1s, compared with 1011s for the alternative formulation.

10. Conclusions.

The passage contains an acknowledgment thanking Hongkai Dai for improving the solver interface used in the numerical experiments.

  • Hongkai Dai is thanked for improving the solver interface used in the paper’s numerical experiments.

Appendix A. Other graph problems in GCS.

The appendix extends the graph-in-convex-sets formulation beyond shortest paths by introducing auxiliary product variables and convex relaxations for general graph constraints.

  • The GCS extension replaces fixed edge weights with convex endpoint-dependent lengths and vertex positions constrained to convex sets.Auxiliary variables represent products between edge-selection variables and vertex positions, producing bilinear constraints.
  • When graph-feasibility constraints are vertex-wise separable, a compact valid MICP results, but it may be weak.The relaxation is exact at integral extreme points of the local flow polytopes.
  • Introducing products for every flow-position pair yields a larger but potentially stronger MICP for coupled graph constraints.This formulation uses n|V||E| continuous variables representing Z := xy^T.
  • The appendix relates the convex relaxation’s dual to the classical network-flow dual, whose variables have a potential interpretation.For the classical formulation, complementary slackness makes the potential jump equal the edge length on shortest-path edges.

B.2. Dual of the SPP in GCS.

The dual of the convexly relaxed SPP in GCS generalizes classical shortest-path potentials to affine functions over vertex sets and bounds their edgewise jumps by convex edge lengths.

  • Dual variables p_v and r_v correspond to flow constraints and auxiliary-variable portions of flow conservation.Additional variables r_s and r_t simplify the presentation.
  • For each vertex, r_v^T x_v + p_v defines a potential over the corresponding convex set, with source-to-target potential jump maximized.The constraints make these potential functions constant over the source and target sets and bound edgewise jumps by edge lengths.
  • Complementary slackness requires tight edgewise potential-length relations on edges carrying positive flow.Edges with zero flow satisfy the condition trivially; for positive flow, the potential jump is tight at the associated auxiliary points.
Loading 2101.11565v5…