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.11565v3cs.DMmath.OC

TL;DR

The paper studies shortest paths where vertex positions vary continuously within convex sets and edge lengths are convex functions of those positions, a generalization that is NP-hard. It develops a perspective-function-based mixed-integer convex formulation with a tight relaxation, reporting globally optimal solutions for large graphs and high-dimensional spaces. The formulation also applies to motion planning, hybrid control, and related graph problems with neighborhoods.

  • Problem

    The paper addresses shortest paths with continuously selectable vertex positions in convex sets and convex position-dependent edge lengths, a formulation that is NP-hard.

  • Method

    The paper formulates the problem as a strong mixed-integer convex program using perspective-function relaxations for naturally arising bilinear constraints.

  • Results

    The convex relaxation is often very tight, enabling globally optimal shortest paths in large graphs and high-dimensional spaces; the formulation also outperforms state-of-the-art techniques on tested control systems.

  • Takeaways & Limitations

    The formulation provides an exact optimization approach for shortest paths and related graph-neighborhood problems across motion planning and hybrid-control applications.

  • Takeaways & Limitations

    The approach can be larger than classical control formulations, scaling quadratically with the number of modes, and the reported random-graph instances are not fully representative.

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 generalization of this classical problem in which the position of each vertex in the graph is a continuous decision variable, constrained to lie in a corresponding convex set. The length of an edge is then defined as a convex function of the positions of the vertices it connects. Problems of this form arise naturally in motion planning of autonomous vehicles, robot navigation, and even optimal control of hybrid dynamical 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 mixed-integer convex formulation based on perspective functions. This formulation has a very tight convex relaxation and makes it possible to efficiently find globally-optimal paths in large graphs and in high-dimensional spaces.

1 Introduction

The paper generalizes shortest paths by allowing graph vertices to choose positions within convex sets and defining edge lengths as convex functions of those positions. It develops a strong mixed-integer convex formulation aimed at globally solving these NP-hard problems across motion-planning, control, and related graph applications.

  • 1 Introduction: Vertices choose continuous positions within associated convex sets, while each traversed edge has a convex position-dependent length.The framework generalizes fixed-edge-length shortest paths by jointly selecting a route and the locations of visited vertices.
  • 1 Introduction: The formulation targets motion planning for robots and autonomous vehicles, and can also represent optimal-control problems for hybrid dynamical systems.Convex sets can represent obstacle-free regions, while graph restrictions encode allowable transitions and operational constraints.
  • 1 Introduction: The problem is NP-hard, so the paper uses a strong mixed-integer convex program solved globally by branch and bound.Its relaxation is built for bilinear constraints using perspective functions, with roots in the Reformulation-Linearization Technique.
  • 1 Introduction: Numerical results report a very tight relaxation that identifies globally optimal paths quickly in large graphs and high-dimensional spaces.The transition-based binary parameterization produces larger but stronger formulations that were orders of magnitude faster in the authors’ computational experience.
  • 1 Introduction: The techniques extend beyond shortest paths to graph problems with neighborhoods, where they can yield exact mixed-integer convex formulations instead of low-dimensional nonconvex methods.Related applications include touring, coverage, spanning-tree, and network-design variants, although the cited existing exact methods are often limited in dimension or scale.
  • 1 Introduction: Approximating convex-set problems by point clusters can be effective in low dimensions but becomes impractical in high dimensions because many points may be required.The paper also contrasts its finite-point-in-regions formulation with Euclidean shortest paths, which require constructing a continuous collision-free path.

2 Problem Statement

The problem seeks a minimum-length source-to-target path while optimizing the locations of visited vertices inside their associated convex sets. Edge lengths may be general convex functions rather than metrics, and graph modifications can permit repeated visits to regions.

  • 2 Problem Statement: A feasible path is a sequence of distinct vertices beginning at source s and ending at target t, with every consecutive pair connected by a directed edge.The visited vertex locations and traversed edges define the path’s geometric and combinatorial components.
  • 2 Problem Statement: The path length is the sum of convex edge-length functions evaluated at the locations of the connected vertices.The optimization ranges over all source-to-target paths and all feasible locations in the corresponding product of convex sets.
  • 2 Problem Statement: Edge lengths need not satisfy metric axioms such as symmetry or the triangle inequality.They are called lengths for modeling purposes, but only the stated convexity assumptions are required.
  • 2 Problem Statement: Repeated visits to a region can be modeled by duplicating its vertex, set, and incident edges, with self-transitions added when needed.The construction extends to any prescribed finite number of visits to the same set.
  • 2 Problem Statement: The model generalizes the classical shortest-path problem when edge-length functions are constants or vertex sets are singletons.Euclidean distance is a common practical choice, but the formulation permits a wider class of convex edge-length functions.
  • 2 Problem Statement: Allowing infinite edge-length values can impose hard constraints coupling consecutive vertex positions and can encode dynamical-system trajectories.This provides a route from the graph formulation to optimal-control models.

3 Complexity Analysis

Unlike classical shortest paths with nonnegative fixed edge costs, the convex-set formulation is NP-hard, including under acyclic graphs. The hardness arises from jointly choosing paths and continuous vertex locations, with reductions covering both cyclic and acyclic settings.

  • 3 Complexity Analysis: Classical shortest paths with nonnegative edge lengths are polynomial-time solvable, for example by Dijkstra’s algorithm, whereas the generalized problem is easy mainly for constant lengths or singleton sets.Cycles, larger sets, nonhomogeneous distance penalties, and carefully designed sets can create difficult instances.
  • 3 Complexity Analysis: Problem (1) is NP-hard via a polynomial reduction from the Hamiltonian-Path Problem.The reduction uses singleton source and target sets, interval sets for other vertices, and squared Euclidean edge lengths so longer paths are cheaper.
  • 3 Complexity Analysis: The reduction remains hard with pairwise disjoint vertex sets, unlike some neighborhood shortest-path variants that become easier under disjointness assumptions.The paper embeds the one-dimensional sets in two dimensions and separates them by small offsets.
  • 3 Complexity Analysis: The complexity analysis asks whether acyclic instances are polynomially solvable and whether hardness depends on the particular squared-distance edge lengths.The acyclic theorem answers the first question negatively, while the broader hardness discussion addresses the second through a separate construction.
  • 3 Complexity Analysis: The theorem establishing acyclic NP-hardness relies on adapting the more involved Euclidean shortest-path complexity analysis.The paper notes that the cyclic reduction is simpler but depends on a particular graph and edge-length construction.
  • 3 Complexity Analysis: Problem (1) is NP-hard even when the graph is acyclic and edge lengths follow the paper’s specified construction.This result rules out attributing hardness solely to graph cycles.

4 Linear-Programming Formulation of the Classical Shortest-Path Problem

The classical shortest-path problem is represented as a unit-flow linear program, providing the foundation for the paper’s mixed-integer convex formulation. Local flow polytopes encode source, target, conservation, and degree structure through their extreme points.

  • 4 Linear-Programming Formulation of the Classical Shortest-Path Problem: With finite nonnegative edge costs, the classical shortest path is formulated as a linear program whose objective minimizes total edge cost.The LP formulation sets the stage for deriving the generalized mixed-integer convex model.
  • 4 Linear-Programming Formulation of the Classical Shortest-Path Problem: Binary variables ϕe indicate whether each edge carries the unit flow from source s to target t.The flow interpretation converts path selection into a network-flow model.
  • 4 Linear-Programming Formulation of the Classical Shortest-Path Problem: The local flow constraints enforce nonnegativity, flow conservation, source injection, target extraction, and a one-unit degree limit at each vertex.Together, these conditions ensure selected edges connect the source to the target without revisiting a vertex beyond the permitted degree.
  • 4 Linear-Programming Formulation of the Classical Shortest-Path Problem: The LP need not explicitly impose binary flow variables because all basic feasible solutions can be shown to be binary.Adding ϕe ∈ {0,1} would therefore not change the optimal value.
  • 4 Linear-Programming Formulation of the Classical Shortest-Path Problem: The degree constraint is redundant for the classical nonnegative-cost LP but becomes necessary in the later mixed-integer convex formulation.Nonnegative cycle costs prevent cycles from improving the classical objective, whereas the generalized model requires the constraint explicitly.
  • 4.1 Extreme Points of the Local Flow Polytopes: At the source, extreme local flows inject one unit through exactly one outgoing edge while all incoming flows are zero.This is represented by the product of a zero vector on incoming edges and a standard-basis vector on outgoing edges.
  • 4.1 Extreme Points of the Local Flow Polytopes: At the target, extreme local flows receive one unit through exactly one incoming edge and have zero outgoing flow.The target polytope is the symmetric counterpart of the source polytope.
  • 4.1 Extreme Points of the Local Flow Polytopes: At an intermediate vertex, an extreme flow either is zero or redirects one incoming unit to one outgoing edge, and these are precisely the binary points of the local flow polytope.This characterization supports the formulation’s path-flow structure.

5 Mixed-Integer Convex Formulation

The paper builds a globally solvable MICP for shortest paths with continuously positioned vertices by using perspective functions to convexify bilinear flow-position constraints, then removes redundant variables to obtain a smaller formulation.

  • 5 Mixed-Integer Convex Formulation: Perspective functions extend the classical shortest-path LP to continuously positioned vertices, producing a bilinear program whose auxiliary variables scale endpoint positions by edge flow.The auxiliary variables collapse to zero when an edge is unused and match endpoint positions when it carries unit flow.
  • 5.1 Bilinear Formulation: The bilinear formulation is difficult to solve because its equality constraints are nonconvex, motivating a mixed-integer convex reformulation solvable globally by branch and bound.Local methods lack convergence guarantees even for simple edge lengths and convex sets.
  • 5.1 Bilinear Formulation: Any local optimum of the bilinear program has an equally costly feasible solution with binary edge flows, so integrality can be recovered cheaply after local optimization.This follows from the integrality property of the underlying flow LP.
  • 5.2 Mixed-Integer Convex Reformulation of the Bilinear Program: The MICP convexifies the bilinear equalities with perspective-based constraints, and with binary flows its feasible set coincides with that of the bilinear program while implicitly enforcing vertex membership.The vertex constraints need not be written explicitly because the MICP constraints imply them.
  • 5.3 Reduced Mixed-Integer Convex Formulation: The definitive formulation removes vertex locations and associated constraints without changing the optimal value, while recovering optimal vertex positions afterward from flows and auxiliary variables.This reduction substantially decreases model size and solution time.
  • 5.3 Reduced Mixed-Integer Convex Formulation: The reduced MICP uses |E| binary and 2d|E| continuous variables, with relaxation size scaling bilinearly in graph size and spatial dimension.Its constraint count is 2|V| + d(|V| − 2) + 2h(d)|E| when each perspective set has h(d) defining constraints.

6 Perspective-Function Toolbox

The perspective-function toolbox gives implementable formulations for common edge lengths, endpoint-coupling constraints, and convex vertex sets, while identifying cases that reduce exactly to the classical shortest-path LP.

  • 6.1.1 When the Edge Lengths ℓe are Constants: For constant nonnegative edge lengths, the MICP is equivalent to the classical shortest-path LP and has zero relaxation gap.The integrality requirement is redundant in this special case.
  • 6.1.2 Positively Homogeneous Edge Lengths: For positively homogeneous edge lengths, perspective costs simplify to the original function applied to auxiliary variables and admit linear or conic implementations for common norms.Examples include ∥A_ex_u + B_ex_v∥ and p-norm formulations.
  • 6.1.3 Squared Norm Edge Lengths: Squared Euclidean-type edge lengths are modeled with a rotated second-order cone that correctly handles positive flow, zero flow, and infeasible zero-flow configurations.The slack cost becomes zero when flow and auxiliary variables are zero.
  • 6.2 Coupling Constraints: An endpoint-coupling constraint (x_u,x_v)∈X_e becomes the hard perspective-set constraint (y_e,z_e,ϕ_e)∈˜X_e.Thus convex coupling constraints can be incorporated directly into the MICP.
  • 6.3 Convex Vertex Sets: Boundedness of the vertex sets is needed so perspective constraints drive auxiliary variables to zero as flow vanishes, making the formulation practical.Without boundedness, the recession cone may prevent this behavior.
  • 6.3.1 Singleton Vertex Sets: When all vertex sets are singletons, the MICP simplifies to the classical shortest-path LP and has zero relaxation gap.The auxiliary variables become linear functions of the flows and can be eliminated.
  • 6.3.2 Polyhedral and Norm-Defined Sets: Polyhedral vertex sets yield linear perspective constraints, while norm-defined sets yield linear constraints for p∈{1,∞} and second-order cones for p=2.These descriptions are directly suitable for standard optimization solvers.

7 Analysis of the Mixed-Integer Convex Formulation

The analysis interprets the formulation as a convex envelope generated from valid inequalities, proves exactness at integral flow patterns, and characterizes the trade-off between relaxation strength and scalability.

  • 7.3 Tightness of the Convex Relaxation: The relaxation is not generally the convex hull, although it equals the McCormick envelope and the convex hull when both underlying sets are intervals in one dimension.The paper explicitly notes that a universally exact characterization would imply P=NP.
  • 7 Analysis of the Mixed-Integer Convex Formulation: The analysis also explains why vertex-position variables can be eliminated and identifies the formulation’s relationship to RLT, Sherali–Adams, and Lovász–Schrijver techniques.These connections provide broader context but are not needed for the remainder of the paper except in Section 10.
  • 7.1 Generalization of the Mixed-Integer Convex Formulation: The perspective of a bounded convex set can be described using its valid inequalities, linking the construction to dual-cone geometry and RLT-style relaxations.The perspective cone and valid-inequality cone are dual for compact convex sets.
  • 7.1 Generalization of the Mixed-Integer Convex Formulation: The convexification method generates linear inequalities by multiplying valid inequalities for flow and position sets, producing a convex relaxation of bilinear product constraints.Perspective operations allow one convex set to be treated through a compact convex representation rather than enumerating all its inequalities.
  • 7.2.1 Finitely-Generated Convex Relaxations Ω′: The proposed use of valid inequalities is exhaustive for each local flow polytope unless additional couplings between nonincident flows are introduced.Redundant inequalities cannot strengthen the formulation through this construction without cutting potentially optimal integer flows.
  • 7.2.2 Tightness of the Envelope Ω′ at the Extreme Points of Φ: At every extreme point of the flow polytope, the convex relaxation exactly matches the original bilinear set, establishing validity of the mixed-integer formulation.This is the geometric reason binary flows recover the original feasible set.
  • 7.3 Tightness of the Convex Relaxation: A stronger polynomial-size MICP can be constructed, but the proposed formulation sacrifices some strength to scale linearly with graph size and perform better in practice.The stronger formulation is generally prohibitive in numerical experience.

8 Dual Optimization Problem

The paper derives a dual of the convex relaxation, interprets it through shortest-path potentials and spatial constraints, and uses weak duality to establish a lower-bound sanity check.

  • 8 Dual Optimization Problem: The dual retains the classical shortest-path interpretation of maximizing the potential difference between source and target, while adding terms for spatial and degree constraints.Edge constraints bound potential jumps using concave expressions associated with edge-length conjugates.
  • 8 Dual Optimization Problem: The dual variables correspond to flow conservation, degree constraints, spatial conservation, and perspective descriptions of the endpoint sets.The construction assigns separate multipliers to the two perspective-set constraints on every edge.
  • 8 Dual Optimization Problem: Weak duality guarantees that the dual optimum is a lower bound on the optimal value of the convex relaxation.The dual is used for bounds rather than an exact primal-dual characterization in the paper.
  • 8.1 Relation to the Classical Shortest-Path Dual: For constant edge lengths, the dual reduces to the classical shortest-path dual because the conjugate contribution reproduces the constant edge-cost constraint.The extra spatial constraint remains specific to the graph-of-convex-sets formulation.
  • 8.3 Lower Bound from Duality: The convex relaxation recovers a lower bound on the optimal shortest-path cost under common distance-based edge lengths and point or full-dimensional source and target sets.The lower bound uses the maximum possible number of edges in a simple path.
  • 8.3 Lower Bound from Duality: The degree constraints are essential for this sanity check because, unlike in the classical LP, they are not redundant in the proposed MICP.The proof relies on an interplay among the dual variables.

9 Application to Optimal Control of Hybrid Dynamical Systems

The paper recasts free- and fixed-horizon optimal control for PWA systems as shortest-path problems over convex mode regions. This formulation represents dynamics through edge costs and enables mixed-integer convex optimization, with size scaling linearly in horizon and quadratically in the number of modes.

  • Application to Optimal Control of Hybrid Dynamical Systems: PWA optimal-control problems can be transcribed as shortest-path problems for both optimized and fixed time horizons.The construction targets discrete-time PWA systems and terminal-set reachability under state and control costs.
  • Problems with Free Time Horizon: Vertices represent source, target, or mode-region visits, while vertex positions encode system states and controls in convex sets.The source fixes the initial state, the target represents the terminal set, and each mode vertex corresponds to a region D_i.
  • Problems with Free Time Horizon: Infinite edge costs exclude state transitions that violate the PWA dynamics, while admissible transitions receive the selected control or state cost.This embeds the system equations directly into the shortest-path edge-length functions.
  • Problems with fixed time horizon: Fixed-horizon control uses time-layered mode vertices, so every source-target path contains exactly K edges and reaches the target after K−1 transitions.Edges connect successive layers and allow every mode pair as a transition.
  • Problems with fixed time horizon: The formulation size grows linearly with the time horizon K and quadratically with the number of modes |I|, unlike classical formulations that are linear in both.The paper argues that the stronger formulation can justify this larger size.

10 Extension of Other Classical Graph Problems

The framework extends beyond shortest paths to classical graph problems with neighborhoods by modeling continuous vertex locations and flow-position products in mixed-integer convex programs. This can replace expensive nonconvex formulations, but handling nonincident flow couplings creates a compactness-strength trade-off.

  • Extension of Other Classical Graph Problems: The proposed techniques can derive strong MICP formulations for neighborhood versions of problems such as TSP and MSTP, which typically use expensive MINCP methods.The paper presents this extension as potentially outperforming existing formulations, while noting that a thorough numerical comparison remains incomplete.
  • Extension of Other Classical Graph Problems: Each graph vertex has a decision position in its convex set, and each edge length depends on the positions of its endpoints.Auxiliary variables y_e and z_e represent products between edge-selection binaries and endpoint positions.
  • Extension of Other Classical Graph Problems: When feasibility constraints couple flows on nonincident edges, the shortest-path convexification structure no longer applies directly.Subtour-elimination constraints are an example of such nonlocal coupling.
  • Extension of Other Classical Graph Problems: Separating local and nonlocal flow constraints yields a compact valid formulation, but the resulting relaxation may be weak.The formulation is exact at binary flow points under the stated assumption Φ_v ⊆ [0,1]^{|E_v|}.
  • Extension of Other Classical Graph Problems: Adding auxiliary variables for every flow-position product produces a larger but stronger formulation.This option introduces d|V||E| auxiliary continuous variables when nonincident products must be represented.

11 Numerical Results

Numerical experiments show that the formulation remains effective on large and high-dimensional instances, while relaxation tightness depends on edge lengths, graph structure, and problem scale. The experiments also demonstrate its application to piecewise-affine optimal control and expose adversarial cases where the relaxation becomes loose.

  • 11.1 Two-Dimensional Example: The Euclidean-distance relaxation is tight for every tested set scale r, including nonzero r values where tightness is not guaranteed by the basic small-set result.Figure 6 compares optimal MICP and convex-relaxation costs as the regions are uniformly shrunk or enlarged.
  • 11.1 Two-Dimensional Example: For squared Euclidean lengths, the relaxation becomes slightly loose for approximately r > 1, although its worst-case gap remains small in the tested two-dimensional instance.The relaxation curve approaches 10.1, the lower bound from Proposition 5, while removing one edge closes the asymptotic gap.
  • 11.2 Large-Scale Random Instances: For squared Euclidean edge lengths, nominal instances remain fast, but dimension d = 20 can produce a 28.9% relaxation gap and solution times exceeding 2 minutes.Increasing edge density also worsens performance, whereas reducing density by adding vertices strongly reduces gaps and computation times.
  • 11.4 Adversarial Examples: Adversarial examples show that cycles, nonhomogeneous edge lengths, and enlarged full-dimensional sets can make the relaxation gap nonzero and increase it substantially.These cases identify structural weaknesses despite the strong performance on the tested random and control instances.

12 Conclusions and Future Works

The paper formulates shortest paths in graphs of convex sets as a strong mixed-integer convex program and finds that its relaxation is often very tight. It also identifies future benchmarking and approximation algorithms as directions for further work.

  • The proposed MICP models an NP-hard shortest-path problem with continuously movable vertices in convex sets and convex edge-length functions.
  • A wide range of numerical tests finds that the MICP's convex relaxation is often very tight.
  • In mixed-integer control problems interpreted as shortest paths, the proposed MICP outperforms state-of-the-art techniques in the reported tests.
  • Future work includes benchmarking against formulations for other graph problems with neighborhoods and developing approximation algorithms for this SPP.

A Alternative Mixed-Integer Convex Formulations

The appendix compares two alternative mixed-integer convex formulations with the proposed MICP. Grouping incident edges yields stronger relaxations, while the larger convex-hull formulation can become computationally burdensome.

  • A.1 Edge-by-Edge Formulation: The edge-by-edge formulation encodes each binary edge disjunction separately using convex-hull constraints rather than weak big-M constraints.For an unused edge, auxiliary variables collapse to zero; for a used edge, they match the endpoint positions.
  • A.1 Edge-by-Edge Formulation: The edge-by-edge formulation is slightly larger than MICP (21), with |E| binary variables and d|V| + 2d|E| continuous variables.Its constraint count is 2|V| + 4h(d)|E|.
  • A.1 Edge-by-Edge Formulation: Using local flow polytopes Φv instead of independent cube bounds exploits tighter flow limits and produces a stronger MICP.The edge-by-edge formulation uses the trivial bound [0,1]|Ev|, whereas the proposed formulation groups edges sharing a vertex.
  • A.2 Convex-Hull Formulation: The alternative convex-hull formulation constructs convex hulls of Ωv ∩ Cv, introducing auxiliary variables for incoming–outgoing edge combinations at intermediate vertices.The variables ϕio represent flow entering through i and leaving through o, while xio matches xv when that flow is active.
  • A.2 Convex-Hull Formulation: Figure 12 compares relaxation costs with the optimal SPP value as the convex sets grow, showing the edge-by-edge and convex-hull alternatives' relative strength.The caption identifies the two plots and the varying set size r.
  • A.2 Convex-Hull Formulation: The convex-hull formulation scales with sums of indegree–outdegree products, creating a size burden that limits performance.
  • A.3 Numerical Comparison: The edge-by-edge relaxation becomes extremely weak as sets grow, while the convex-hull relaxation is indistinguishable from MICP (21).For both edge-length functions, the edge-by-edge relaxation converges to zero and fails to recover the simple lower bound.
  • A.3 Numerical Comparison: In the optimal-control example, the edge-by-edge formulation has a 91% relaxation gap and solves in 10.3 s, whereas the convex-hull formulation has an 18% gap but takes 588 s.The edge-by-edge formulation remains an order of magnitude slower than MICP (21), while the convex-hull formulation is much larger.

B.1 Sketch of Proof of Theorem 2

The NP-hardness proof reduces 3-SAT to the shortest-path problem by constructing a layered three-dimensional arrangement of convex sets. Each satisfying assignment corresponds to a candidate shortest path, and the construction preserves acyclicity.

  • The reduction from 3-SAT stacks two-dimensional convex sets in three-dimensional space to encode exponentially many assignment-dependent s-t paths.The source is placed at the top and the target at the bottom of the stack.
  • The constructed convex-set environment uses bounded sets and guarantees sequential traversal, ensuring that the edge set contains no cycles.

B.2 Proof of the Claims from Section 4.1

The appendix proves the structure of local flow polytopes and establishes the convex-hull representation used in the formulation. It decomposes feasible flows into convex combinations of extreme flow patterns and lifts this decomposition to the auxiliary formulation.

  • For nonterminal vertices, the extreme points of the local flow polytope are the zero flow and paired unit flows represented by Δ|Ein_v| × Δ|Eout_v|.The proof verifies both inclusions between the polytope and the convex hull of these points.
  • Any nonzero feasible local flow is decomposed into paired incoming–outgoing unit flows plus a zero-flow component.The coefficients are nonnegative and sum to one because of nonnegativity and flow conservation.
  • The appendix notes a solver-setting correction for one reported result: Mosek required MSK IPAR INTPNT SOLVE FORM to be set to MSK SOLVE PRIMAL.
  • The convex-hull proof represents a feasible point as a convex combination of points indexed by extreme flows, preserving the original flow, position, and auxiliary variables.

B.4 Proof of Proposition 4

The proof establishes Proposition 4 by constructing a dual-feasible assignment whose objective matches the primal optimal value, then invoking weak duality and strong duality. Fenchel–Young inequalities, conjugates of perspective functions, flow constraints, and support functions certify feasibility and nonnegative objective differences.

  • B.4 Proof of Proposition 4: Rearranging the primal–dual objective difference by edge and multiplier groups decomposes it into nonnegative terms using flow, degree, and spatial-flow conservation constraints.The proof applies conservation of flow for p_v and r_v, and degree feasibility plus q_v nonnegativity for the q_v terms.
  • B.4 Proof of Proposition 4: Fenchel–Young inequality bounds each perspective edge-length term, while its conjugate is an indicator of T_e and evaluates to zero under the dual constraints.The remaining terms are nonnegative because cone duality and the primal and dual constraints enforce the required inner-product inequalities.
  • B.4 Proof of Proposition 4: For the specialized edge length, the conjugate yields a hidden equality r_u+a_e=r_v−α_e and the dual inequality p_u−p_v−q_u+b_e+β_e≤−ℓ∗(−r_v+α_e).If the hidden equality fails, the relevant supremum is infinite and the dual is infeasible.
  • B.4 Proof of Proposition 4: The proof’s central strategy is to synthesize a dual feasible solution with cost equal to the optimal value of (40), so weak duality implies the proposition.The derivation begins by reformulating (40) with indicator functions and deriving its conjugate-function dual.
  • B.4 Proof of Proposition 4: Strong duality for (40) and (66) holds under mild assumptions on ℓ and the convex sets, allowing the constructed dual assignment to attain the same optimal value.The assignment defines r_v, a_e, b_e, α_e, β_e, p_v, and q_v using a decision variable r and support functions, then verifies all dual constraints.
  • B.4 Proof of Proposition 4: The assignment satisfies q_v≥0 because ℓ(0)=0 implies ℓ∗≥0, while support-function differences are nonnegative; the remaining constraints follow directly from support-function definitions.The hidden equality and potential-jump conditions are verified by substitution and simplification.
Loading 2101.11565v3…