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.

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

• 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

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