FlowPreserving 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
\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 onedimensional 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 RealWorld Instances
 Python implementation of homotopy method and marginal cost approximation
 Tests on realworld 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 nonparametric instances with the FrankWolfe method
Solution for the SiouxFalls traffic network.
Network  $n$  $m$  MCA  FrankWolfe (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 (MitteP.F.C.)  843  1376  60.2 s  15.3 s 
ChicagoSketch  546  2176  117.5 s  116.2 s 
GasLib11  8  8  2.7 s  0.1 s 
GasLib24  18  19  6.2 s  0.3 s 
GasLib40  34  39  16.9 s  0.5 s 
GasLib134  87  86  19.4 s  0.1 s 
GasLib135  106  141  80.6 s  1.9 s 
GasLib582  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.
@article{KlimmWarode2021,
author = {Max Klimm and Philipp Warode},
doi = {10.1287/moor.2021.1151},
journal = {Mathematics of Operations Research},
number = {1},
pages = {812846},
title = {Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs},
volume = {47},
year = {2022},
}
We develop algorithms solving parametric flow problems with separable, continuous, piecewise quadratic, and strictly convex cost functions. The parameter to be considered is a common multiplier on the demand of all nodes. Our algorithms compute a family of flows that are each feasible for the respective demand and minimize the costs among the feasible flows for that demand. For single commodity networks with homogenous cost functions, our algorithm requires one matrix multiplication for the initialization, a rank 1 update for each nondegenerate step and the solution of a convex quadratic program for each degenerate step. For nonhomogeneous cost functions, the initialization requires the solution of a convex quadratic program instead. For multicommodity networks, both the initialization and every step of the algorithm require the solution of a convex program. As each step is mirrored by a breakpoint in the output this yields outputpolynomial algorithms in every case.
2021
 Approximate Parametric Computation of MinimumCost Flows with Convex Costs (Per Joachims, Max Klimm and Philipp Warode)
Preprint, 2021.
@techreport{JoachimsKlimmWarode2021,
arxiv = {2203.13146},
author = {Per Joachims and Max Klimm and Philipp Warode},
title = {Approximate Parametric Computation of MinimumCost Flows with Convex Costs},
year = {2021},
}
This paper studies a variant of the minimumcost flow problem in a graph with convex cost functions, where the demands at the vertices are functions depending on a onedimensional parameter $\lambda$. We devise two algorithmic approaches for the approximate computation of parametric solutions for this problem. The first approach transforms an instance of the parametric problem into an instance with piecewise quadratic cost functions by interpolating the marginal cost functions. The new instance can be solved exactly with an algorithm we developed in prior work. In the second approach, we compute a fixed number of nonparametric solutions and interpolate the resulting flows yielding an approximate solution for the original, parametric problem. For both methods we formulate explicit bounds on the step sizes used in the respective interpolations that guarantee relative and absolute error margins. Finally, we test our approaches on realworld traffic and gas instances in an empirical study.
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 ACMSIAM Symposium on Discrete Algorithms, pp. 2728–2747.
@inproceedings{KlimmWarode2020,
author = {Max Klimm and Philipp Warode},
booktitle = {SODA 2020 – Proc. 31st ACMSIAM Symposium on Discrete Algorithms},
doi = {10.1137/1.9781611975994.166},
pages = {27282747},
title = {Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block {Laplacians}},
year = {2020},
}
We settle the complexity of computing an equilibrium in atomic splittable congestion games with playerspecific affine cost functions $l_{e,i}(x) = a_{e,i}x + b_{e,i}$ showing that it is $\mathsf{PPAD}$complete. To prove that the problem is contained in $\mathsf{PPAD}$, we develop a homotopy method that traces an equilibrium for varying flow demands of the players. A key technique is to describe the evolution of the equilibrium locally by a novel block Laplacian matrix. This leads to a path following formulation where states correspond to supports that are feasible for some demands and neighboring supports are feasible for increased or decreased flow demands. A closer investigation of the block Laplacian system allows to orient the states giving rise to unique predecessor and successor states thus putting the problem into $\mathsf{PPAD}$. For the $\mathsf{PPAD}$hardness, we reduce from computing an approximate equilibrium of a bimatrix winlose game. As a byproduct of our reduction we further show that computing a multiclass Wardrop equilibrium with classdependent affine cost functions is $\mathsf{PPAD}$complete as well. As a byproduct of our $\mathsf{PPAD}$completeness proof, we obtain an algorithm that computes all equilibria parametrized by the players' flow demands. For playerspecific costs, this computation may require several increases and decreases of the demands leading to an algorithm that runs in polynomial space but exponential time. For playerindependent costs only demand increases are necessary. If the coefficients be,i are in general position, this yields an algorithm computing all equilibria as a function of the flow demand running in time polynomial in the output.
2019
 Computing all Wardrop Equilibria parametrized by the Flow Demand (Max Klimm and Philipp Warode)
SODA 2019 – Proc. 30th ACMSIAM Symposium on Discrete Algorithms, pp. 917–934.
@inproceedings{KlimmWarode2019,
author = {Max Klimm and Philipp Warode},
booktitle = {SODA 2019 – Proc. 30th ACMSIAM Symposium on Discrete Algorithms},
doi = {10.1137/1.9781611975482.56},
pages = {917934},
title = {Computing all {Wardrop} Equilibria parametrized by the Flow Demand},
year = {2019},
}
We develop an algorithm that computes for a given undirected or directed network with flowdependent piecewise linear edge cost functions all Wardrop equilibria as a function of the flow demand. Our algorithm is based on Katzenelson's homotopy method for electrical networks. The algorithm uses a bijection between vertex potentials and flow excess vectors that is piecewise linear in the potential space and where each linear segment can be interpreted as an augmenting flow in a residual network. The algorithm iteratively increases the excess of one or more vertex pairs until the bijection reaches a point of nondifferentiability. Then, the next linear region is chosen in a simplexlike pivot step and the algorithm proceeds. We first show that this algorithm correctly computes all Wardrop equilibria in undirected singlecommodity networks along the chosen path of excess vectors. We then adapt our algorithm to also work for discontinuous cost functions which allows to model directed edges and/or edge capacities. Our algorithm is outputpolynomial in nondegenerate instances where the solution curve never hits a point where the cost function of more than one edge becomes nondifferentiable. For degenerate instances we still obtain an outputpolynomial algorithm computing the linear segments of the bijection by a convex program. The latter technique also allows to handle multiple commodities.