Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

# Instantaneous Dynamic Equlibrium Flows

Lukas Graf1, Tobias Harks1, Leon Sering2

1 Augsburg University, 2 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

## 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)$.

## 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)$
Lukas Graf
IDE Flows - Introduction & Model Lukas Graf
IDE Flows - Existence & Construction Lukas Graf
IDE Flows - Termination Time & PoA Lukas Graf
IDE Flows - Complexity Lukas Graf