Graph contractions
Logistics networks keep growing in size and complexity, rendering them intractable for traditional optimization techniques. We investigate a contraction framework reducing the networks to manageable size, while preserving the routability of demands at a given cost.
The general idea is to algorithmically generate appropriate approximations of the underlying network with a lower complexity in terms of the represented data. Then, the optimization problem at hand is solved for the contracted network. Finally, the solution for the smaller network is expanded to a solution of the full network.
Graph contractions & shortest path
We are interested in reducing the size of a graph by contracting as many edges $C \subseteq E$ as possible without changing the distance between any pair of vertices $\operatorname{dist} (u,v)$ at most by a given tolerance.
Distance preserving graph contractions
Objective: For given $\alpha \geq 1, \beta > 0$ find a maximal subset $C \subseteq E$ of edges such that $\alpha \operatorname{dist}_{G/C} + \beta \geq \operatorname{dist}_G$.
Minimum Cost Flows
We consider the minimum cost flow problem
\[
\min \sum_{e \in E} F_e (x_e) \text{ s.t. } \mathbf{x} \text{ is a flow vector satisfying the demands } \mathbf{b}
\]
for given edge cost functions $F_e$ and flow demands $b_v$ at the vertices. With the correct choice of cost functions we can model many real world applications as minimum cost flow problems.
Electricty
$F_e (x_e) = \frac{1}{2} r_e x_e^2$
Gas Flows in Pipelines
$F_e (x_e) = \frac{1}{3} r_e |x_e| x_e^2$
Traffic flows
$F_e (x_e) = \tau_e (1 + \alpha_e x_e^4)$
Logistics
implicitly given function
Images:
LoggaWiggler,
norqin,
emkanicepic,
Pexels
via Pixabay, under Pixabay License
-
Objective:
Find a function $C(\mathbf{b})$ that describes the cost of a minimum cost flow in a (sub-)graph $G$ in dependence of the in- and outflows $\mathbf{b}$
-
Motivation:
Given such a function $C(\mathbf{b})$ for a subcomponent $C$, we can treat $C$ as a black box in the minimum cost flow computation and possible reduce the complexity of computing the minimum cost flow
-
Tool:
We use a parametric formulation of the minimum cost flow problem in order to understand the behavior of the minimum cost flow depending on the in- and outflows
Parametric Minimum Cost Flow Problem
Consider the parametric variant of the minimum cost flow problem
\begin{equation} \label{eq:parametricMCF}
\min \sum_{e \in E} F_e (x_e) \text{ s.t. } \mathbf{x} \text{ is a flow vector satisfying the demands } \mathbf{b} (\lambda)
\end{equation}
where the demands are parametrized by a one-dimensional parameter $\lambda$.
-
We call a function $\lambda \mapsto \mathbf{x} (\lambda)$ that solves \eqref{eq:parametricMCF} a mincost flow function.
-
$C(\mathbf{x}(\lambda)) := \sum_{e \in E} F_e (x_e (\lambda))$ denotes the cost of the mincost flow parametrized by $\lambda$.
-
For $\alpha \geq 1, \beta \geq 0$, we call a function $\lambda \mapsto \tilde{\mathbf{x}} (\lambda)$ an $(\alpha, \beta)$-approximate mincost flow function if
\[
C (\mathbf{x}(\lambda)) \leq \alpha C (\tilde{\mathbf{x}} (\lambda)) + \beta
\]
for all $\lambda \in [0, \lambda^{\max}]$ and some maximal parameter $\lambda^{max}$.
Parametric Minimum Cost Flows with Piecwise Quadratic Cost Functions
-
For (piecewise) quadratic costs, the exact mincost flow function can be computed since the optimality conditions depending on $f_e := F'_e$ are piecewise linear.
-
Computation is based on a homoptopy method following the piecewise linear line of optimal dual potentials $\lambda \mapsto \mathbf{\pi} (\lambda)$.
-
Method runs in output polynomial time $\mathcal{O} (n^2 K)$, where $K$ is the number of breakpoints of the output function. In general, $K$ can be exponential in the size of the graph.
- Start with a potential $\mathbf{\pi}(\lambda)$ of the optimal solution for $\lambda = 0$
-
While $\lambda < \infty$:
- Identify a region containing $\mathbf{\pi} (\lambda)$
- Compute the line segment of the solution in the region by solving a linear system of equations
- Do a pivoting step to the next region and next $\mathbf{\pi} (\lambda)$
Parametric Minimum Cost Flows with Convex Costs
- For convex cost function, we can compute approximate mincost flow functions by approximating the marginal cost $f_e := F'_e$ with linear splines.
- Explicit bounds $\delta(\alpha, \beta)$ for the interpolation step sizes guarantee that the outcome is an $(\alpha, \beta)$-optimal solution
- Approximate marginal cost $f_e := F'_e$ of the edges with linear splines $\tilde{f}_e$ with step sizes $\delta(\alpha, \beta)$
- Create new instance $I'$ with (piecewise quadratic) edge cost $\tilde{F}_e (x) := \int_0^{x} \tilde{f}_e (s) ds$.
- Solve the instance $I'$ with the homotopy method from above.
A Computational Study on Real-World Instances
- Python implementation of homotopy method and marginal cost approximation
- Tests on real-world traffic and gas pipeline network instances with random parametric demands
- The implementation is fast and in part even competitive with the minimum cost flow computation for non-parametric instances with the Frank-Wolfe method
Solution for the Sioux-Falls traffic network.
Network | $n$ | $m$ | MCA | Frank-Wolfe (for fixed demand) |
SiouxFalls | 24 | 76 | 1.3 s | 4.0 s |
Berlin (Tiergarten) | 321 | 545 | 10.0 s | 6.2 s |
Anaheim | 416 | 914 | 4.1 s | 21.0 s |
Berlin (Mitte-P.-F.-C.) | 843 | 1376 | 60.2 s | 15.3 s |
Chicago-Sketch | 546 | 2176 | 117.5 s | 116.2 s |
GasLib-11 | 8 | 8 | 2.7 s | 0.1 s |
GasLib-24 | 18 | 19 | 6.2 s | 0.3 s |
GasLib-40 | 34 | 39 | 16.9 s | 0.5 s |
GasLib-134 | 87 | 86 | 19.4 s | 0.1 s |
GasLib-135 | 106 | 141 | 80.6 s | 1.9 s |
GasLib-582 | 268 | 278 | 218.4 s | 12.1 s |
Average runtimes of MCA with random demands for traffic instances from the Transporation Networks Library
and gas networks from the GasLib.
References
2022
- Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs (Max Klimm and Philipp Warode)
Mathematics of Operations Research, 47(1):812–846, 2022.
2020
- Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians (Max Klimm and Philipp Warode)
SODA 2020 – Proc. 31st ACM-SIAM Symposium on Discrete Algorithms, pp. 2728–2747.
2019
- Computing all Wardrop Equilibria parametrized by the Flow Demand (Max Klimm and Philipp Warode)
SODA 2019 – Proc. 30th ACM-SIAM Symposium on Discrete Algorithms, pp. 917–934.
Extended version "Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs" appeared in Math. Oper Res. 2021