Instantaneous Dynamic Equlibrium Flows

Lukas Graf¹, Tobias Harks¹, Leon Sering²

¹ Augsburg University, ² Technische Universität Berlin

↑ Discrete Model

(unsplittable flow particles, discrete time steps)

Continuous Model ↓

(infinitesimal flow particles, continuous time)

Physical Model

A directed graph $G = (V,E)$
Edge travel times $\tau_e \in \INs$ (here $\tau_e=1$)
Edge capacities $\nu_e \in \INs$ (here, mostly, $\nu_e \in \Set{1,\infty}$)
Single sink $t \in V$
Network inflow rates $u_v: \IR_{\geq 0} \to \IR_{\geq 0}$
(piece-wise constant, finitely lasting
with finitely many steps)
Inflow $\gt$ capacity $\implies$ queues form
$f_e^+(\theta) \gt \nu_e$ (length $q_e(\theta)$)

Behavioral Model

The current travel time at time $\theta$ on edge $e$ is: \[c_e(\theta) := \tau_e + q_e(\theta)/\nu_e\]

A flow is in Instantaneous Dynamic Equilibrium (IDE) if the following holds:
Whenever positive flow enters an edge, this edge must lie on a currently shortest path towards the respective sink (w.r.t. $c$).

\[f^+_{vw}(\theta) > 0 \implies \ell_v(\theta) = c_{vw}(\theta) + \ell_w(\theta)\]

where $\ell_v(\theta) \coloneqq \begin{cases}0, & \text{if } v=t \\ \min_{e=vw}\{\ell_w(\theta) + c_e(\theta)\}, &\text{else}\end{cases}$

(we then call edge $vw$ active at time $\theta$)

Questions:

Existence
&
Construction?

Termination Time
&
Price of Anarchy?

Complexity?

Existence

Input: A single-sink network $\mathcal{N} = (G,\tau,\nu,u,t)$
Output: An IDE flow $f$ in $\mathcal{N}$
(1) Let $f$ be an IDE flow up to time $\theta = 0$

(2) While not all flow has reached $t$ Do

(3) .. Extend $f$

(3) .. Assume all $f_e^{^-}$ constant on $[\theta,\theta+\alpha_0)$

(3) .. Sort nodes s.th. $\ell_{v_1}(\theta) \leq \ell_{v_2}(\theta) \leq \dots$
(4) .. For $i = 1, \dots, n$ Do

(5) .... Find constant IDE extension of $f$ at $v_i$
(5) .... for some $[\theta,\theta+\alpha_i]$ with $\alpha_i \gt 0$

(6) .. Extend $f$ up to $\theta \coloneqq \theta+\min\Set{\alpha_i}$

We can compute a maximal constant extension at a single node in polynomial time.

→ Waterfilling algorithm:

Distribute outflow from $v$:

Remaining: 7.0

Remaining: 6.0

Remaining: 1.5

Remaining: 0.0

Distribute to (currently) active edges $vw$ s.th.:

$f^+_{vw}(\theta) > 0 \implies \phantom{\rDeriv}\ell_{v}(\theta) = \phantom{\rDeriv} c_{vw}(\theta) + \phantom{\rDeriv}\ell_{w}(\theta)$
$f^+_{vw}(\theta) = 0 \implies \phantom{\rDeriv}\ell_{v}(\theta) \leq \phantom{\rDeriv} c_{vw}(\theta) + \phantom{\rDeriv}\ell_{w}(\theta)$

$f^+_{vw}(\theta) > 0 \implies \rDeriv\ell_{v}(\theta) = \rDeriv c_{vw}(\theta) + \rDeriv\ell_{w}(\theta)$
$f^+_{vw}(\theta) = 0 \implies \rDeriv\ell_{v}(\theta) \leq \rDeriv c_{vw}(\theta) + \rDeriv\ell_{w}(\theta)$

The set of active edges may change if

an edge becomes newly active or
the queue of an active edge runs empty.

$\implies \alpha_i > 0$.

In single-sink networks IDE flows exist.

Lemma above & Zorn's lemma

Existence (Multi-Sink)

In multi-sink networks IDE flows always exist
(even for more general inflow rate functions $u_i$).

Given an IDE flow $f$ up to some time $\theta_0$, extend $f$ up to some time $\theta_0+\varepsilon$.
Calculate the node-inflows at time $\theta_0$.
Order nodes by their distance to sink $t$.

Let $K := \{g\,|\,g$ extension of $f$ on $[\theta_0, \theta_0+\tau_{\min})$ (not necessarily IDE)$\}$.
Consider the mapping $\mathcal{A}: K \to L^2([\theta_0,\theta_0+\tau_{\min}))^{I \times E}, g=(g_{i,e}) \mapsto h = (h_{i,e}),$
where $h_{i,vw}(\theta) := \quad\ell_{w,i}(\theta) + \quad c_{vw}(\theta)\quad - \ell_{v,i}(\theta)$ $= 0 \iff vw$ is active

$v$

$w$

$t_i$

Then: $g \in K$ is IDE extension $\iff \langle g, \mathcal{A}(g)\rangle = 0$ $\iff \langle \mathcal{A}(g),g'-g\rangle \geq 0$ f.a. $g' \in K$

Such a $g$ always exists ($\mathcal{A}$ weak-strong-cont., $K$ non-empty, closed, convex, bounded).

$s_1$

$s_2$

$t_2$

$t_1$

Termination

In single-sink networks $G$ all IDE flows terminate
within at most $4U\tau_G$.

In an acyclic graph the termination time is $\tau_{\max}+U$.

Without queues the active edges form a static acyclic graph.

With only small queues the active edges form a static acyclic graph.

A subgraph $H \subseteq G$ containing the sink $t$
as well as all its shortest paths towards the sink
is sink-like for some interval $[a,b]$ if the sum of

current flow volume within $H$ and
the cummulative inflow into $H$ over $[a,b]$

is at most $\frac{1}{2}$.
Let $v \in G\setminus H$ be closest to $t$. Then $H+v$ is sink-like for $\left[a,b-\sum_{e \text{ edge between } v \text{ and } H}(\tau_e + \frac{1}{\nu_e})\right]$.
$\implies$ If $H := \{t\}$ is sink-like for $\tau_G+|E|$, the flow terminates.
$\implies$ The sink has inflow of at least $\frac{1}{2}$ all $2\tau_G$ time steps.

In single-sink networks $G$ the PoA for IDE flows is in $\bigO\left(U\tau_G\right)$.

Termination (Multi-Sink)

There exists a multi-sink network where all IDE flows cycle forever.

For IDEs in multi-sink-networks the Price of Anarchy is $\infty$.

$s_1$

$t_1$

$s$

Price of Anarchy

For single-sink instances with parameters $U$ and $\tau_G$ the Price of Anarchy is in $\mathcal{O}(U\tau_G)$.

For single-sink instances with parameters $U$ and $\tau_G$ the Price of Anarchy is in $\mathcal{O}(U\tau_G) \cap \Omega(\phantom{U\log\tau_G})$.

For single-sink instances with parameters $U$ and $\tau_G$ the Price of Anarchy is in $\mathcal{O}(U\tau_G) \cap \Omega(U\log\tau_G)$.

Output Complexity

Arbitrarily small extension phases!
IDE has $\Omega(U)$ phases
(non-periodic!)
Instance of size $\bigO(\log U)$

The number of phases of an IDE flow can be exponential in the encoding size of the network.

IDE flows with forever lasting network inflow rates may never reach a steady state.

Construction (Acyclic Networks)

Input: An acyclic single-sink network $\mathcal{N}$
Output: An IDE flow $f$ in $\mathcal{N}$
(1) Let $f$ be an IDE flow up to time $\theta = 0$
(2) While not all flow has reached $t$ Do
(3) .. Sort nodes s.th. $\ell_{v_1}(\theta) \leq \ell_{v_2}(\theta) \leq \dots$
(4) .. For $i = 1, \dots, n$ Do
(5) .... Find constant IDE extension of $f$ at $v_i$
(5) .... for some $[\theta,\theta+\alpha_i]$
(6) .. Extend $f$ up to $\theta \coloneqq \theta\,+\,\min\Set{\alpha_i}$

Input: An acyclic single-sink network $\mathcal{N}$
Output: An IDE flow $f$ in $\mathcal{N}$
(1) Let $f$ be an IDE flow up to time $\theta = 0$
(2) Fix some topological order $v_1 \lt v_2 \lt \dots$
(3) While not all flow has reached $t$ Do
(4) .. For $i = 1, \dots, n$ Do
(5) .... Find constant IDE extension of $f$ at $v_i$
(5) .... for some $[\theta,\theta+\alpha_i]$
(6) .. Extend $f$ up to $\theta \coloneqq \theta\,\,+$$\,\,\min\Set{\alpha_i}$

Input: An acyclic single-sink network $\mathcal{N}$
Output: An IDE flow $f$ in $\mathcal{N}$
(1) Let $f$ be an IDE flow up to time $\theta = 0$
(2) Fix some topological order $v_1 \lt v_2 \lt \dots$
(3) While not all flow has reached $t$ Do
(4) .. For $i = 1, \dots, n$ Do
(5) .... Find piecewise constant IDE extension
(5) .... of $f$ at $v_i$ for $[\theta,\theta+1]$
(6) .. Extend $f$ up to $\theta \coloneqq \theta\,\,+$$\,\,1$

$h_i: [\theta_1, \theta_2] \to \IR_{\geq 0}, \theta \mapsto \tau_{vw_i}+\frac{\queue_{vw_i}(\theta)}{\nu_{vw_i}} + \ell_{w_i}(\theta)$

Given a node $v$ and an IDE $f$ up to $\theta_1$, extended to an IDE up to $\theta_2 > \theta_1$ for all nodes closer to $t$ than $v$, s.th.

the inflow into node $v$ is constant over $[\theta_1,\theta_2]$ and
the labels at all nodes closer to $t$ thant $v$ are linear.

Than we can extend $f$ at $v$ to an IDE up to time $\theta_2$ in a finite number of subphases.

For acyclic networks the above algorithm constructs an IDE flow in finite time.

(in at most $\bigO\left(P(2(\Delta+1)^{4^\Delta+1})^{T\abs{V}}\right)$ sub-phases)

Construction (General Networks)

We only need the network to be acyclic for the fixed topological order.

The subgraph of active edges is always acyclic.

For general networks: Show that we only need to change the topological order a finite number of times.

For general single-sink networks the extension algorithm computes an IDE flow in finite time.

(in at most $\bigO\left(P(2(\Delta+1)^{4^\Delta+1})^{T\abs{V}\cdot \abs{E}/C}\right)$ phases)

NP-Hardness

The following decision problems are NP-hard:

Given a network and a specific edge: Is there an IDE flow not using this edge?
Given a network and a specific edge: Is there an IDE flow using this edge?
Given a network and some time $T$: Is there an IDE terminating before $T$?
Given a network and some number $k$: Is there an IDE flow with at most $k$ phases?

Reduction from 3Sat:

\[\big(x_1 \,\,\,\vee\,\,\, \neg x_1 \,\,\,\vee\,\,\, x_2\big) \,\,\qquad\qquad\wedge\,\,\qquad\qquad \big(\neg x_1 \,\,\,\vee\,\,\, \neg x_2 \,\,\,\vee\,\,\, \neg x_3\big)\]

Paper: arxiv.org/abs/1811.07381 | Presentation: graffl.gitlab.io/ide-flow-talks/index_AS.html