Technische Universität Berlin

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

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.

Electricity
Electricty
$F_e (x_e) = \frac{1}{2} r_e x_e^2$
Gas Flow
Gas Flows in Pipelines
$F_e (x_e) = \frac{1}{3} r_e |x_e| x_e^2$
Traffic
Traffic flows
$F_e (x_e) = \tau_e (1 + \alpha_e x_e^4)$
Logistics
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.
  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)$
Visualization of the Homotopy Method

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
Sioux Falls Traffic network

Solution for the Sioux-Falls traffic network.

Network$n$$m$MCAFrank-Wolfe

(for fixed demand)

SiouxFalls24761.3 s4.0 s
Berlin (Tiergarten)32154510.0 s6.2 s
Anaheim4169144.1 s21.0 s
Berlin (Mitte-P.-F.-C.)843137660.2 s15.3 s
Chicago-Sketch5462176117.5 s116.2 s
GasLib-11882.7 s0.1 s
GasLib-2418196.2 s0.3 s
GasLib-40343916.9 s0.5 s
GasLib-134878619.4 s0.1 s
GasLib-13510614180.6 s1.9 s
GasLib-582268278218.4 s12.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 ( and )
    Mathematics of Operations Research, 47(1):812–846, .
    [pdf] [doi]

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