Faculties
DE / EN

Flow-Preserving Graph Contractions

Project description

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 $$\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)$$ 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.
1. Start with a potential $\mathbf{\pi}(\lambda)$ of the optimal solution for $\lambda = 0$
2. While $\lambda < \infty$:
1. Identify a region containing $\mathbf{\pi} (\lambda)$
2. Compute the line segment of the solution in the region by solving a linear system of equations
3. 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
1. Approximate marginal cost $f_e := F'_e$ of the edges with linear splines $\tilde{f}_e$ with step sizes $\delta(\alpha, \beta)$
2. Create new instance $I'$ with (piecewise quadratic) edge cost $\tilde{F}_e (x) := \int_0^{x} \tilde{f}_e (s) ds$.
3. 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.

2022

• Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs ( and )
Mathematics of Operations Research, 47(1):812–846, .

2020

• Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians ( and )
SODA 2020 – Proc. 31st ACM-SIAM Symposium on Discrete Algorithms, pp. 2728–2747.
[doi]

2019

• Computing all Wardrop Equilibria parametrized by the Flow Demand ( and )
SODA 2019 – Proc. 30th ACM-SIAM Symposium on Discrete Algorithms, pp. 917–934.
[doi]
Extended version "Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs" appeared in Math. Oper Res. 2021