A Faster Parametric Search for the Integral Quickest Transshipment Problem

We only prove the statement for $\alpha$-parametric instances, as the reasoning is analogous for $\delta$-parametric instances. Let $X\subseteq S\cup \{\widehat{s},\check{s}\}$ be an arbitrary subset of terminals. Given that we assume the transshipment instance to be feasible, we have $v(X)\ge 0$. Remember that the maximum out-flow $o^{\alpha }(X)$ is the value of a maximum flow over time from a super-source $s^{+}$ to a super-sink $s^{-}$, where infinite-capacity, zero-transit arcs are used to connect $s^{+}$ to every source in $S^{+}\cap X$ and to connect every sink in $S^{-}\setminus X$ to $s^{-}$. Using this definition, we derive the following observations regarding $o(X)$:

1. O1

   If $X$ contains neither $\widehat{s}$ nor $\check{s}$, then maximum out-flow $o^{\alpha }(X)$ coincides with the out-flow $o(X)$ in the original instance.

2. O2

   If $X$ contains $\check{s}$, then all flow traveling from $s^{+}$ to $s$ can bypass the $\alpha$-capacity arc $(\widehat{s},s)$ and move along the infinite-capacity arcs $(s^{+},\check{s})$ and $(\check{s},s)$ instead. As a consequence, we have $o^{\alpha }(X)=o(X)$.

We refer the reader back to Figure 1 for a visual intuition. Combining these observations with the parametric balances $b^{\alpha }(\widehat{s})={\mathrm{\Delta }}^{\alpha }$ and $b^{\alpha }(\check{s})=b(\check{s})-{\mathrm{\Delta }}^{\alpha }$, we prove Lemma 12 by considering the following three complementary cases.

1. (I)

   If $\widehat{s}\in X$ and $\check{s}\in X$, then it follows that

   $$b^{\alpha }(X)=b^{\alpha }(X\setminus \{\widehat{s},\check{s}\})+b^{\alpha }(\widehat{s})+b^{\alpha }(\check{s})\stackrel{\text{Def. of }{b}^{\alpha }}{=}{b}^{\alpha }(X\setminus \{\widehat{s},\check{s}\})+b(\check{s})=b(X\setminus \{\widehat{s}\})=b(X).$$

   Together with Observation 2 we obtain $v^{\alpha }(X)=v(X)\ge 0$, meaning that $X$ cannot be a violated set.

2. (II)

   If $\widehat{s}\notin X$ and $\check{s}\in X$, then it follows that , which, together with Observation 2, implies that $X$ cannot be a violated set since $v^{\alpha }(X)\ge v(X)\ge 0$.

3. (III)

   If $\widehat{s}\notin X$ and $\check{s}\notin X$, then $b^{\alpha }(X)=b(X)$ and therefore $X$ cannot be a violated set as it follows from Observation 1 that $v^{\alpha }(X)=o^{\alpha }(X)-b^{\alpha }(X)=o(X)-b(X)=v(X)\ge 0$.

Hence, $X$ can only be a violated set of $({𝒩}^{\alpha },b^{\alpha },T)$ if $\widehat{s}\in X$ and $\check{s}\notin X$. $◀$

Hoppe and Tardos [4] proved the property from Lemma 12 for the special case of the infeasible parameter value ${\delta }^{\ast }-1$ and used it to show that there exists a set $X$ satisfying $\widehat{Q}\subset X\subset \widehat{R}$ which is violated for ${\delta }^{\ast }-1$ and tight for ${\delta }^{\ast }$. We employ similar arguments to show that this also holds for all infeasible $\alpha ,\delta \in {\mathbb{N}}_0$.

We only prove the statement for MaximizeAlpha, as the proof for MinimizeDelta is analogous. Let $X^{\ast }$ be an arbitrary minimizer of $v^{\alpha }$ with . It follows from Lemma 12 that $\widehat{s}\in X^{\ast }$ and $\check{s}\notin X^{\ast }$. Next, we show that the set $X≔Q\cup (X^{\ast }\cap \widehat{R})$ is also a minimizer of $v^{\alpha }$. For this, we analyze the tightness of the sets $Q$, $\widehat{Q}$, and $\widehat{R}$:

• $\mathrm{■}$

  $Q$ was chosen to be a tight set for $(𝒩,b,T)$. This also does not change in the parametric instance as $\widehat{s},\check{s}\notin Q$ and hence $v^{\alpha }(Q)=v(Q)=0$.

• $\mathrm{■}$

  $\widehat{Q}$ is tight, since $b^{\alpha }(\widehat{Q})=b^{\alpha }(Q)+{\mathrm{\Delta }}^{\alpha }\stackrel{Q\text{ tight}}{=}{o}^{\alpha }(Q)+o^{\alpha }(\widehat{Q})-o^{\alpha }(Q)=o^{\alpha }(\widehat{Q})$.

• $\mathrm{■}$

  $\widehat{R}$ is tight because $R$ is tight and $\widehat{s},\check{s}\in \widehat{R}$ directly imply $o^{\alpha }(\widehat{R})=o(R)=b(R)=b^{\alpha }(\widehat{R})$.

Having shown that $Q$ and $\widehat{R}$ are tight sets, we study how tight sets and minimizers of $v^{\alpha }$ behave under union and intersection. For this purpose, let $Y\in \{Q,\widehat{R}\}$. It follows from submodularity of $v^{\alpha }$ that

Note that both summands on the left hand side are non-positive, since otherwise one of them would be smaller than the minimum value $v^{\alpha }(X^{\ast })$. Hence, either both summands are negative, or one is equal to zero while the other equals the minimum value of $v^{\alpha }$. In other words, exactly one of the following properties must hold:

1. (1)

   Both $X^{\ast }\cup Y$ and $X^{\ast }\cap Y$ are violated sets of $v^{\alpha }$.

2. (2)

   Either $X^{\ast }\cup Y$ or $X^{\ast }\cap Y$ is a minimizer, while the other set is tight.

We apply this case distinction to the cases where $Y=Q$ and $Y=\widehat{R}$:

• $\mathrm{■}$

  Let $Y=\widehat{R}$, then Lemma 12 states that a violated set cannot contain $\check{s}$, implying that $v^{\alpha }(X^{\ast }\cup \widehat{R})\ge 0$ since $\check{s}\in \widehat{R}$. This means that $X^{\ast }\cap \widehat{R}$ is a minimizer of $v^{\alpha }$.

• $\mathrm{■}$

  Consider $Y=Q$ and the minimizer $X^{\ast }\cap \widehat{R}$. We rule out $Q\cap (X^{\ast }\cap \widehat{R})=Q\cap X^{\ast }$ as a violated set since $\widehat{s}\notin Q\cap X^{\ast }$. Therefore, $Q\cup (X^{\ast }\cap \widehat{R})$ is a minimizer.

Finally, observe that the minimizer $X=Q\cup (X^{\ast }\cap \widehat{R})$ not only satisfies $\widehat{Q}\subseteq X\subseteq \widehat{R}$ because $\widehat{s}\in X^{\ast }\cap \widehat{R}$ but also $\widehat{Q}\subset X\subset \widehat{R}$ since $\widehat{Q}$ and $\widehat{R}$ are tight. $◀$

Lemma 13 allows us to determine feasibility of a parameter value by minimizing the restricted functions ${\tilde{v}}^{\alpha }:2^{\widehat{R}\setminus \widehat{Q}}\to \mathbb{Z}$ and ${\tilde{v}}^{\delta }:2^{\widehat{R}\setminus \widehat{Q}}\to \mathbb{Z}$ with ${\tilde{v}}^{\alpha }(X)≔v^{\alpha }(\widehat{Q}\cup X)$ and ${\tilde{v}}^{\delta }(X)≔v^{\delta }(\widehat{Q}\cup X)$. For future use, we define the functions ${\tilde{o}}^{\alpha }$, ${\tilde{o}}^{\delta }$, ${\tilde{b}}^{\alpha }$, and ${\tilde{b}}^{\delta }$ analogously.

This brings us to the main result in this section.

The obvious advantage of this result is the reduction of the domain of the submodular functions of interest to $\widehat{R}\setminus \widehat{Q}$. Although we have $R=S$ and $Q=\mathrm{\varnothing }$ at the beginning, the difference becomes smaller over the course of Hoppe and Tardos’ algorithm, until both sets are eventually equal. This yields a significant practical speed-up in later iterations of the algorithm. Moreover, the reduction brings further practical and theoretical advantages, which we discuss in the following section.

Our argument is structured as follows: We first prove that ${\tilde{o}}^{\alpha }⊏{\tilde{o}}^{\alpha +1}$ holds for all $\alpha \in {\mathbb{N}}_0$ and then use this result to prove that ${\tilde{v}}^{\alpha }$ also forms a strong map sequence with ${\tilde{v}}^{\alpha }⊏{\tilde{v}}^{\alpha +1}$. The general claim ${\tilde{v}}^{\alpha }⊏{\tilde{v}}^{{\alpha }^{\prime }}$ then immediately follows by transitivity of $\le$.

Let $\alpha \in {\mathbb{N}}_0$ be arbitrary but fixed. We construct an auxiliary network $𝔑$ with nodes $V(𝔑)≔V({𝒩}^{\alpha })\cup \{𝔰\}$ and arcs $A(𝔑)≔A({𝒩}^{\alpha })\cup \{𝔞≔(𝔰,s)\}$, where $s$ is the source that was replaced by $\check{s}$ in the first phase of the algorithm. For the new arc, we set $u_{𝔞}=1$ and ${\tau }_{𝔞}=0$. An example network for a given source $\widehat{s}$ is depicted in Figure 3.

Let $𝔬(X)$ be the max out-flow function for network $𝔑$ restricted to the domain $\widehat{R}\setminus \widehat{Q}\cup \{𝔰\}$. Notice how adding $𝔰$ to a set of terminals $X\subseteq \widehat{R}\setminus \widehat{Q}\cup \{𝔰\}$ with $\widehat{s}\in X$ and $\check{s}\notin X$ is equivalent to increasing $\alpha$ by one, as flow cannot bypass the arcs $(𝔰,s)$ and $(\widehat{s},s)$ through $(\check{s},s)$. Formally, it holds for every set $X$ with $X\subseteq \widehat{R}\setminus \widehat{Q}$ that

1. 1.

   $𝔬(X)={\tilde{o}}^{\alpha }(X)$, and

2. 2.

   $𝔬(X\cup \{𝔰\})={\tilde{o}}^{\alpha +1}(X)$.

Clearly, the function $𝔬$ is also submodular. Hence, given two sets $X\subseteq Y\subset \widehat{R}\setminus \widehat{Q}$, the definition of submodularity in Equation 2 can be restated as

Combining Equation 4 with all our previous observations, it follows that the sets $X$ and $Y$ satisfy

Hence, we have shown that ${\tilde{o}}^{\alpha }⊏{\tilde{o}}^{\alpha +1}$ holds for every parameter value $\alpha$. Finally, recall our definition of ${\tilde{v}}^{\alpha }$ as ${\tilde{v}}^{\alpha }(X)={\tilde{o}}^{\alpha }(X)-{\tilde{b}}^{\alpha }(X)$ for any $X\subseteq \widehat{R}\setminus \widehat{Q}$. Due to the strong map property of ${\tilde{o}}^{\alpha }$, we get for all $X\subseteq Y\subseteq \widehat{R}\setminus \widehat{Q}$ that

therefore proving that ${\tilde{v}}^{\alpha }⊏{\tilde{v}}^{\alpha +1}$. Thus, by transitivity of $\le$, our claim ${\tilde{v}}^{\alpha }⊏{\tilde{v}}^{{\alpha }^{\prime }}$ holds. $◀$

Next, we utilize a similar argument to prove that ${\tilde{v}}^{\delta }$ forms a strong map sequence. Here, we rely on our specific definition of the $\delta$-parametric network ${𝒩}^{\delta }$.

The general approach is identical to the proof of Theorem 17. That is, we show that ${\tilde{o}}^{\delta }$ forms a strong map sequence with ${\tilde{o}}^{\delta -1}⊐{\tilde{o}}^{\delta }$ for $\delta \ge 1$. Afterwards, we transfer this result to ${\tilde{v}}^{\delta -1}$ and ${\tilde{v}}^{\delta }$. The general claim then directly follows from the transitivity of $\le$.

Again, let $\delta \in \mathbb{N}$ be arbitrary but fixed. We construct an auxiliary network $𝔑$ with nodes $V(𝔑)≔V({𝒩}^{\delta })\cup \{𝔰\}$ and arcs $A(𝔑)≔(A({𝒩}^{\delta })\setminus \{(\widehat{s},s)\})\cup \{𝔞≔(𝔰,s),\widehat{a}≔(\widehat{s},𝔰)\}$, $s$ is the source that was replaced by $\check{s}$ in the first step of the algorithm. Additionally, let $u_{\widehat{a}}=u_{𝔞}=1$, ${\tau }_{𝔞}=\delta -1$ and ${\tau }_{\widehat{a}}=1$. An example for a source $\widehat{s}$ is given in Figure 4.

Again, $𝔬(X)$ denotes the maximum out-flow function for this network restricted to the domain $\widehat{R}\setminus \widehat{Q}\cup \{𝔰\}$. In this construction, we have replaced the arc $(\widehat{s},s)$ by a path consisting of arcs $(\widehat{s},𝔰)$ and $(𝔰,s)$ with a combined transit time of $\delta$. As a consequence, the maximum out-flow $𝔬(X)$ remains unchanged for sets $X\subseteq \widehat{R}\setminus \widehat{Q}$. If $𝔰\in X$ and $\widehat{s}\in X$, on the other hand, both sources compete for access to the arc $(𝔰,s)$. Then, the flow out of $X$ is maximized by sending all flow from $𝔰$. Formally, it holds for every set $X\subseteq \widehat{R}\setminus \widehat{Q}$ that

1. 1.

   $𝔬(X)={\tilde{o}}^{\delta }(X)$, and

2. 2.

   $𝔬(X\cup \{𝔰\})={\tilde{o}}^{\delta -1}(X)$

These observations plus the second definition of submodularity from Equation 2 imply for all sets $X\subseteq Y\subseteq \widehat{R}\setminus \widehat{Q}$ that

Therefore, the function ${\tilde{o}}^{\delta }$ forms a strong map sequence with ${\tilde{o}}^{\delta -1}⊐{\tilde{o}}^{\delta }$. Finally, by the same arguments as in the proof of Lemma 17, the parametric function ${\tilde{v}}^{\delta }$ forms a strong map sequence with ${\tilde{v}}^{\delta }⊐{\tilde{v}}^{{\delta }^{\prime }}$ as claimed. $◀$

In the following section, we use the strong map property and the resulting nested sequences of minimizers to construct new parametric search algorithms for $v^{\alpha }$ and $v^{\delta }$ .

Let $\alpha ,\delta \in {\mathbb{N}}_0$ be arbitrary but fixed parameter values. We set $Z≔X\cup \widehat{Q}$ and decompose ${\tilde{v}}^{\alpha }(X)$ (and, analogously, ${\tilde{v}}^{\delta }(X)$) as

Observe that we can treat the term $o^{\alpha }(Q)-b(Z\setminus \{\widehat{s}\})$ as constant: since $\widehat{s},\check{s}\notin Q$, the out-flow $o^{\alpha }(Q)$ is identical for all $\alpha \in {\mathbb{N}}_0$ (or $\delta \in {\mathbb{N}}_0$). Similarly, the value of $b(Z\setminus \{\widehat{s}\})$ does not depend on $\alpha$ or $\delta$.

We now prove monotonicity using this simplification. For MaximizeAlpha, the monotonicity ${\tilde{v}}^{\alpha }(X)\ge {\tilde{v}}^{\alpha +1}(X)$ holds if and only if ${\tilde{o}}^{\alpha }(X)-{\tilde{o}}^{\alpha }(\mathrm{\varnothing })\ge {\tilde{o}}^{\alpha +1}(X)-{\tilde{o}}^{\alpha +1}(\mathrm{\varnothing })$ is true, which follows directly from the strong map property ${\tilde{o}}^{\alpha }⊏{\tilde{o}}^{\alpha +1}$ shown in the proof of Lemma 17. Similarly, replacing $\alpha$ with $\delta$ in Equation 5, it follows from ${\tilde{o}}^{\delta }⊐{\tilde{o}}^{\delta +1}$ that ${\tilde{o}}^{\delta }(X)-{\tilde{o}}^{\delta }(\mathrm{\varnothing })\ge {\tilde{o}}^{\delta +1}(X)-{\tilde{o}}^{\delta +1}(\mathrm{\varnothing })$ and thus ${\tilde{v}}^{\delta }(X)\le {\tilde{v}}^{\delta +1}(X)$ holds. $◀$

The monotonicity and strong map property of ${\tilde{v}}^{\alpha }$ and ${\tilde{v}}^{\delta }$ allow us to introduce new parametric search algorithms for MaximizeAlpha (cf. Algorithm 1) and MinimizeDelta (cf. Algorithm 2). In their core, they follow a rather simple approach similar to algorithms by Schlöter, Skutella, and Tran [12, 11]: we start with an infeasible parameter value ${\alpha }_1$ or ${\delta }_1$ and a corresponding minimizer $X_1$ of ${\tilde{v}}^{{\alpha }_1}$ or ${\tilde{v}}^{{\delta }_1}$. Possible initial values are ${\alpha }_1≔{\alpha }_{\text{max}}=n{U}_{\text{max}}$ and ${\delta }_1≔0$ [4]. Next, we alternate between two steps jump and check until the current minimizer $X_i$ is no longer violated. In the jump step, we compute the largest parameter value ${\alpha }_{i+1}$ or the smallest parameter value ${\delta }_{i+1}$ such that the previous minimizer $X_i$ is no longer violated. Note that this step is, in essence, an integral parametric min-cost flow problem with one parametrized arc. Afterwards, the check step finds a minimizer $X_{i+1}$ for the new value ${\alpha }_{i+1}$ and ${\delta }_{i+1}$.

In the check step, we use the results of the previous sections in order to restrict the search for minimizers to $X_{i+1}\subset X_i$. We will show in the following that this restriction is actually feasible. Note that the restriction not only reduces the search space in each iteration to $|X_i|$ terminals, but also limits MaximizeAlpha and MinimizeDelta to at most $|S|$ iterations, since the length of the chain $X_1\supset X_2\supset \mathrm{\dots }$ is limited by $|\widehat{R}\setminus \widehat{Q}|\le |S|$.

We first show by induction that if ${\alpha }_i$ is infeasible, then there exists a minimizer $X_i$ of ${\tilde{v}}^{{\alpha }_i}$ with $X_i\subset X_{i-1}$, where $X_0=\widehat{R}\setminus \widehat{Q}$.

By definition, $X_1$ is a minimizer of ${\tilde{v}}^{{\alpha }_1}$. Let ${\alpha }_i$ and ${\alpha }_{i+1}$ be infeasible, and assume that $X_i$ is a minimizer of ${\tilde{v}}^{{\alpha }_i}$. We have , since otherwise contradicts the choice of ${\alpha }_{i+1}$ as feasible for $X_i$. Together with Lemma 17, this implies the relation ${\tilde{v}}^{{\alpha }_i}⊐{\tilde{v}}^{{\alpha }_{i+1}}$. Therefore, we have $X_{i+1}^{\text{min}}\subseteq X_i^{\text{min}}\subseteq X_i$ due to Lemma 16, with $X_j^{\text{min}}$ being the minimal minimizer of ${\tilde{v}}^{{\alpha }_j}$ for $j\in \{i,i+1\}$. Since ${\alpha }_{i+1}$ is infeasible with , and, by definition, ${\tilde{v}}^{{\alpha }_{i+1}}(X_i)\ge 0$, we even have $X_{i+1}^{\text{min}}\subset X_i$. Hence, $X_{i+1}^{\text{min}}$ is a feasible choice for $X_{i+1}$ in Algorithm 1.

Recall that Algorithm 1 terminates after at most $|S|$ iterations. Let ${\alpha }_{i^{\ast }}$ be the value returned by the algorithm, and let $X_{i^{\ast }}$ be the minimizer generated in the final iteration $i^{\ast }$. If ${\alpha }_{i^{\ast }}$ were not feasible, then $X_{i^{\ast }}$ would be a minimizer with . However, since the algorithm terminates, it follows that ${\alpha }_{i^{\ast }}$ is feasible.