Optimal transport paths with capacity induced cost function

Basic Information

• Paper ID: 2510.10557
• Title: Optimal transport paths with capacity induced cost function
• Authors: Haotian Sun, Qinglan Xia
• Classification: math.OC (Optimization and Control)
• Publication Date: October 12, 2025
• Paper Link: https://arxiv.org/abs/2510.10557v1

Abstract

This paper extends the study of branched optimal transport with capacity constraints by generalizing the $M_α$ cost to $M_{α,c}$, a cost function that incorporates capacity constraints directly into the cost structure. Equipped with the $M_{α,c}$ cost, we establish the existence of optimal transport paths, derive $M_{α,c}$-related inequalities, provide decomposition results for arbitrary general transport paths, and characterize the appearance of straight line segments in optimal transport paths.

Research Background and Motivation

Problem Background

The core problem addressed in this research concerns capacity constraints in branched optimal transport. Traditional Monge-Kantorovich transport problems characterize measure transport using transport maps and transport plans, where the total cost is independent of the actual "paths" connecting source and target points.

Research Motivation

1. Limitations of Existing Methods: In prior work 11, the authors employed "multi-paths" to handle transport problems with capacity constraints, but this approach suffers from convergence issues, as demonstrated in Example 1.2, where transport paths satisfying $θ(x) ≤ c$ cannot guarantee convergence.
2. Deficiencies of Multi-path Methods: Although multi-path methods resolve convergence issues, they remain deficient. As shown in Remark 1.3 and Figure 3, there exist admissible transport paths whose weights on each edge are at most $c$, whose boundary equals the sum of multi-path boundaries, yet whose $M_α$ cost is less than or equal to the multi-path $M_α$ cost.
3. Necessity of Methodological Innovation: A revised characterization method for capacity-constrained branched transport is needed such that the set of admissible transport paths "expands" relative to multi-paths while still "containing" the condition $θ(x) ≤ c$ in some sense.

Core Contributions

1. Proposed a new cost function $M_{α,c}$: Generalized the traditional $M_α$ cost to $M_{α,c}$ by directly incorporating capacity constraints into the cost function
2. Established existence of optimal transport paths: Proved existence theorems for optimal transport paths under the new cost function
3. Derived $M_{α,c}$-related inequalities: Including subadditivity, monotonicity, and other important properties
4. Provided decomposition theory for transport paths: Proved that arbitrary transport paths can be decomposed into paths with weights equal to integer multiples of capacity and paths with weights less than capacity
5. Analyzed the appearance of straight line segments in optimal paths: Demonstrated that in optimal transport paths, portions with weights equal to integer multiples of capacity tend to be transported via straight line segments

Methodology Details

Problem Formulation

Given two equal-mass Radon measures $μ^-$ and $μ^+$ supported on compact sets in $\mathbb{R}^m$, a parameter $α ∈ [0,1]$, and capacity constraint $c > 0$, find a transport path $T ∈ \text{Path}(μ^-, μ^+)$ that minimizes the $M_{α,c}$ cost.

Core Cost Function Design

For any $T = τ(M, θ(x), ξ(x)) ∈ \text{Path}(μ^-, μ^+)$, the new transport cost is defined as:

$M_{α,c}(T) := c^α \cdot \int_M \left\lfloor \frac{θ(x)}{c} \right\rfloor + \left(\frac{θ(x)}{c} - \left\lfloor \frac{θ(x)}{c} \right\rfloor\right)^α dH^1$

where $\lfloor θ(x)/c \rfloor$ denotes the greatest integer not exceeding $θ(x)/c$.

Key Properties of the Cost Function

1. Boundary Behavior

• As $c → ∞$: $\lim_{c→∞} M_{α,c}(T) = M_α(T)$ (recovers traditional $M_α$ cost)
• As $c → 0$: The cost is dominated by the integer part $c^α \int_M \lfloor θ(x)/c \rfloor dH^1$

2. Auxiliary Function Properties

Define the auxiliary function $H_{c,α}(x) := \lfloor x/c \rfloor + (x/c - \lfloor x/c \rfloor)^α$, which possesses the following properties:

• For $α ∈ (0,1]$: $H_{c,α}(x)$ is strictly increasing, concave, and continuous
• For $α = 0$: $H_{c,α}(x)$ is increasing and piecewise constant with jump discontinuities at integer points
• Subadditivity: $H_{c,α}(x_1 + x_2) ≤ H_{c,α}(x_1) + H_{c,α}(x_2)$

Technical Innovations

1. Implicit Treatment of Capacity Constraints

Unlike explicit constraints $θ(x) ≤ c$, the new method handles capacity constraints implicitly through the cost function, avoiding convergence issues.

2. Integer-Fractional Decomposition Idea

The $\lfloor θ(x)/c \rfloor$ term in the cost function represents the subdivision of "total" weight at each point into several components, each with weight not exceeding $c$.

3. Compatibility with Multi-path Methods

Proposition 3.6 proves that for multi-paths $\vec{T} ∈ \text{Path}_c(μ^-, μ^+)$, we have $M_{α,c}(T) ≤ M_α(\vec{T})$, where $T = \sum_{k=1}^∞ T_k$.

Theoretical Results

Existence Theorem

Theorem 3.4: Given equal-mass Radon measures $μ^-, μ^+$ supported on compact sets, for any $α ∈ [0,1]$ and $c > 0$, there exists $T^* ∈ \text{Path}(μ^-, μ^+)$ such that $M_{α,c}(T^*) ≤ M_{α,c}(T)$ for all $T ∈ \text{Path}(μ^-, μ^+)$.

Important Inequalities

Lemma 3.3: For any rectifiable 1-current $T$, $M(T) ≤ c^{1-α}M_{α,c}(T) ≤ M(T) + c \cdot \text{size}(T)$

Proposition 3.5: For $h ∈ \mathbb{R}$,

• When $0 ≤ h ≤ 1$: $M_{α,c}(hT) ≤ h^α M_{α,c}(T)$
• When $h ≥ 1$: $h^α M_{α,c}(T) ≤ M_{α,c}(hT)$

Path Decomposition Theorem

Theorem 4.3: Given a transport path $T$ and any cycle $R$ on it, if the condition $\max_{x∈N} \left(\frac{θ(x)}{c} - \left\lfloor \frac{θ(x)}{c} \right\rfloor\right) + \min_{x∈N} \left(\frac{θ(x)}{c} - \left\lfloor \frac{θ(x)}{c} \right\rfloor\right) ≤ 1$ is satisfied, then acyclic transport paths $T_1, T_2$ can be found such that:

• $∂T = ∂(T_1 + T_2)$
• $θ_1(x) = c \cdot n(x)$, where $n(x) ∈ \mathbb{Z}^+$
• $θ_2(x) ≤ c$
• $M_{α,c}(T_1 + T_2) = M_{α,c}(T_1) + M_{α,c}(T_2) ≤ M_{α,c}(T)$

Straight Line Segment Appearance Theorem

Proposition 4.5 and Corollary 4.6: In optimal transport paths, for portions with weights equal to integer multiples of capacity, if a path connecting two points exists, it must be a straight line segment.

Geometric Analysis

Angle Calculations

In the simple "2-to-1 point" transport case, the paper provides detailed angle calculations at the confluence point. Let the confluence point be $t'$, and the unit direction vectors be $\vec{n}_1, \vec{n}_2, \vec{n}_3$. The optimality condition is: $k_1\vec{n}_1 + k_2\vec{n}_2 + k_3\vec{n}_3 = 0$

where $k_i$ are the corresponding adjusted costs. The angle formula is: $\cos(θ_1) = \frac{k_1^2 + k_3^2 - k_2^2}{2k_1k_3}$

Effects of Capacity Parameter

• As $c → ∞$: Angle behavior matches that of traditional $M_α$ cost
• As $c → 0$: $\lim_{c→0} k_1/k_3 = m_1/(m_1 + m_2)$, resulting in collinearity of all points

Related Work

This paper builds upon the following important works:

1. Monge-Kantorovich Transport Theory 1,7: Classical optimal transport theory
2. Branched Optimal Transport 8,9: Using transport paths rather than transport maps
3. Geometric Measure Theory 4,6: Rectifiable currents and flat norm theory
4. Capacity-Constrained Transport 11: Authors' prior work on multi-path methods
5. Lower Semicontinuity Theory 2: Key tool for proving existence

Conclusions and Discussion

Main Conclusions

1. The new cost function $M_{α,c}$ successfully incorporates capacity constraints into transport cost, avoiding convergence issues from explicit constraints
2. Optimal transport paths exist under the new cost and possess desirable mathematical properties
3. Arbitrary transport paths can be decomposed into "integer capacity" and "fractional capacity" components
4. Integer capacity portions in optimal paths tend to use straight line segments for transport

Limitations

1. Computational Complexity: The new cost function involves floor operations, potentially increasing numerical computation complexity
2. Parameter Sensitivity: The cost function is sensitive to the capacity parameter $c$, particularly when $c$ is very small
3. High-Dimensional Generalization: Geometric analysis such as angle calculations is primarily conducted in two dimensions; higher dimensions are more complex

Future Directions

1. Numerical Algorithm Development: Design efficient numerical methods for solving $M_{α,c}$ optimization problems
2. Application Extensions: Apply the theory to practical network design, logistics optimization, and related problems
3. Stochastic Cases: Consider scenarios where demand and supply are stochastic

In-Depth Evaluation

Strengths

1. Strong Theoretical Innovation: Cleverly solves capacity constraint problems by modifying the cost function, avoiding technical difficulties of explicit constraints
2. High Mathematical Rigor: Complete proofs covering existence, uniqueness, decomposition properties, and multiple aspects
3. Clear Geometric Intuition: Provides good geometric intuition through concrete angle calculations and examples
4. Complete Theoretical Framework: Constructs a comprehensive theoretical system from basic definitions to advanced properties

Weaknesses

1. Insufficient Practical Application Verification: The paper focuses primarily on theoretical development, lacking verification in practical application scenarios
2. Missing Computational Methods: No concrete numerical algorithms provided for solving the optimization problem
3. Lack of Quantitative Comparison with Existing Methods: Absent quantitative performance comparison with existing methods such as multi-path approaches

Impact

1. Theoretical Contribution: Provides a new mathematical framework for capacity-constrained optimal transport theory
2. Methodological Value: The approach of handling constraints through cost function design has general methodological value
3. Application Potential: Shows application prospects in network optimization, supply chain management, and related fields

Applicable Scenarios

1. Network Design: Optimal network design considering edge capacity limits
2. Logistics Optimization: Supply chain optimization with transport capacity constraints
3. Urban Planning: Traffic network planning considering road capacity
4. Biological Networks: Modeling biological systems such as vascular and neural networks

References

The paper cites 23 important references, primarily including:

• Classical optimal transport works: Ambrosio et al. 1, Villani 7
• Branched optimal transport: Xia 8,9
• Geometric measure theory: Lin & Yang 4, Simon 6
• Authors' prior work: Xia & Sun 10,11

This paper achieves important theoretical progress, providing a new mathematical framework for capacity-constrained optimal transport problems. While practical application verification requires further strengthening, its theoretical innovation and mathematical rigor make it a significant contribution to the field.