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.

\( \newcommand{\IN}{\mathbb{N}} \newcommand{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IC}{\mathbb{C}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\U}{\mathfrak{U}} \newcommand{\coloneqq}{:=} \newcommand{\Set}[1]{\left\{#1\right\}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\Re}{\mathrm{Re}} \newcommand{\Im}{\mathrm{Im}} \newcommand{\clos}[1]{\overline{#1}} \newcommand{\inte}[1]{\mathring{#1}} \newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)} \newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)} \newcommand{\Ind}{\unicode{x1D7D9}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\queue}{z} \)

Computational Complexity of Constructing
Instantaneous Dynamic Equilibrium Flows

Lukas Graf, Tobias Harks
Augsburg University

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)
  • Flow given by edge in- and outflow rates $f_e^+, f_e^-$
  • Whenever $f_e^+(\theta) > \nu_e$ a queue $\queue_e(\theta)$
    forms at the start of edge $e$
← sink

Behavioral Model

Dynamic Equilibrium/Nash Flow Glaskugel: Symbolbild fuer in die Zukunft sehen /Murmeltier: Symbolbild fuer Erfahrung durch Wiederholen
Instantaneous Dynamic Equilibrium (IDE) Navi
\theta u_v \theta u_w
v w t x (\tau_{vx}, \nu_{vx}) (\tau_{xt}, {\tiny\nu_{xt}}) (1, \infty) (1, {\tiny 1}) \queue_{xt}(\theta)=1
Particles choose a path once at their source
which is the fastest in hindsight.
Particles choose an edge at every node
which is on a currently fastest path.
The instantaneous travel time at time \(\theta\) on edge \(e\) is $c_e(\theta) \coloneqq \tau_e + \queue_e(\theta)/\nu_e$

The instantaneous distance from node $v$ to sink $t$ is $\ell_v(\theta) \coloneqq \begin{cases}0, & \text{if } v=t \\ \min_{e=vw}\{\ell_w(\theta) + c_e(\theta)\}, &\text{else}\end{cases}$

A flow over time is an Instantaneous Dynamic Equilibrium (IDE) if the following holds:

$f^+_e(\theta) > 0 \implies \ell_v(\theta) = \ell_w(\theta) + c_e(\theta)$ for all edges $e = vw \in E$ and times $\theta \in \IR_{\geq 0}$.

(i.e. flow may only enter active edges)

$c_{xt}(\theta) = 1+1$
$\ell_v(\theta) = 3$

Main Questions of the Talk

Part I: Upper Bound
Can we compute an IDE flow in finite time?
Part II: Lower Bound
How hard is computing an IDE flow?

An Algorithm for Computing IDE Flows

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}$

\theta u_v \theta u_w v w t x
We can compute a maximal constant extension at a single node in polynomial time.
→ Waterfilling algorithm: \tiny 1 \tiny 2 \tiny 3 \tiny 4 \tiny 5 \tiny 1 \tiny 2 \tiny 3 \tiny 4 \tiny 5 \tiny 1 \tiny 2 \tiny 3 \tiny 4 \tiny 5
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 with finitely lasting network inflow rates all IDE flows terminate within finite time.
Show that a finite number of phases suffices.

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)$
v w_1 w_2 w_3 w_4
\ell_{w_1} \ell_{w_2} \ell_{w_3} \ell_{w_4}
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)

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.
Define lazy set of active edges $\tilde{E}$, where
  • we add edges whenever they become active (i.e. edge $vw$ when $\ell_v(\theta) = \ell_w(\theta) + c_{vw}(\theta)$)
  • we remove edges when $\tilde{E}$ contains a cycle (remove "worst offender", i.e. edge $vw$ with maximal $\ell_w(\theta) - \ell_{v}(\theta)$)
$\tilde{E}$ is always acyclic and contains all active edges.

  $\implies$ Algorithm may use a topological order w.r.t. $\tilde{E}$

For any network there exists a constant $C$: $\tilde{E}$ can change at most $\abs{E}$ time during any interval of length $C$.
There is a (flow independend!) bound $L$ on the maximum rate of change for all label functions $\ell_v$.
  • When $vw$ is added we have $\ell_v(\theta) = \ell_w(\theta) + c_{vw}(\theta) \geq \ell_w(\theta) + 1$
  • When $vw$ is removed we have $\ell_v(\theta) \leq \ell_w(\theta)$
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)

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

Output Complexity

  • Instance of size $\bigO(\log U)$
  • IDE has $\Omega(U)$ phases
    (non-periodic!)
  • Arbitrarily small extension phases
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.
\theta \small U \small 2 u_s \theta \small 3 \queue_{vt} \theta \small 2 \queue_{wx} s v w x t

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)\]
c_1 c_2 x_1 \neg x_1 x_2 \neg x_2 x_3 \neg x_3 t s \mathcal{N}' \theta \small 1 u_{c_i}
! Possibly exponentially many phases
! NP-Hardness of several natural properties

Conclusion

Images:

Paper: https://arxiv.org/abs/2007.07808 (working paper)
Slides: https://graffl.gitlab.io/ide-flow-talks/index_Dagstuhl.html
Lukas Graf
Computational Complexity of IDE - Introduction Lukas Graf
Computational Complexity of IDE - Part I: Upper Bound Lukas Graf
Computational Complexity of IDE - Part II: Lower Bound Lukas Graf
Computational Complexity of IDE - Conlusion Lukas Graf