A Hypergraph Network Simplex Algorithm

Abstract

We describe a network simplex algorithm for the minimum cost flow problem on graph-based hypergraphs which are directed hypergraphs of a particular form occurring in railway rotation planning. The algorithm is based on work of Cambini, Gallo, and Scutellà who developed a hypergraphic generalization of the network simplex algorithm, see Cambini et al, Mathematical Programming, 78, 195–217, 1997, [6]. Their main theoretical result is the characterization of basis matrices. We give a similar characterization for graph-based hypergraphs and show that most operations of the simplex algorithm can be done combinatorially by exploiting the underlying digraph structure.

1 Directed and Graph-Based Hypergraphs

A directed hypergraph is usually defined as a pair $(V,\mathcal A)$ where V is a finite set of vertices and $\mathcal A$ is a set of pairs $a = (T(a),H(a))$ where T(a), H(a) are disjoint subsets of V. The set T(a) is called the tail and H(a) the head of hyperarc a. A good survey on directed hypergraphs can be found in [1]. Inspired by an application to railway rotation planning Borndörfer et al. [2] defined directed hypergraphs slightly differently. Namely, they start with an ordinary directed graph and define a hyperarc to be a set of pairwise disjoint arcs.

Definition 1

Let $D=(V,A)$ be a directed graph. A directed hypergraph based on D is a pair $H=(V,\mathcal A)$ where V is the vertex set of D and $\mathcal A$ is a set of non-empty subsets $E\subseteq A$ consisting of vertex-disjoint arcs. In this setting we call H a graph-based hypergraph.

A graph-based hypergraph can be seen as a special kind of directed hypergraph by setting $T(E)=\{v\in V: \exists w\in V, (v,w)\in E\}$ and $H(E)=\{v\in V: \exists w\in V, (w,v)\in E\}$ for $E\in \mathcal A$. For $v\in V$ we set $\delta ^{in}(v):=\{E\in \mathcal A: v\in H(E)\}$ and $\delta ^{out}(v):=\{E\in \mathcal A: v\in T(E)\}$. Using linear programming terminology the minimum cost flow problem can be stated as follows.

Definition 2

Given a graph-based hypergraph $H=(V, \mathcal A)$, and functions $b:V\rightarrow \mathbb R$, $c:\mathcal A\rightarrow \mathbb R_{\ge 0}$, $u:\mathcal A\rightarrow \mathbb R\cup \{\infty \}$ the minimum cost hyperflow problem is the following linear optimization problem

$$\begin{aligned} \min \sum _{E\in \mathcal A}c(E)f(E)&\nonumber \\ \sum _{E\in \delta ^{in}(v)}f(E)- & {} \sum _{E\in \delta ^{out}(v)}f(E) = b(v)\ \forall v\in V \end{aligned}$$

(1)

$$\begin{aligned} 0\le&f(E)\le&u(E)\ \forall E\in \mathcal A. \end{aligned}$$

(2)

For integral input data b, c, u there always exists an integral min-cost flow in directed graphs. For the special case that every hyperarc has at most one vertex in its head and b is nonnegative, the integrality of b implies the existence of an integral min-cost hyperflow which can be found by a combinatorial primal-dual algorithm, see [3]. However, this is not true for the min-cost hyperflow problem in general. In particular, it is $\mathcal NP$-hard to find an integral min-cost hyperflow (e.g. by reduction to 3D-Matching); even if all hyperarcs consist of at most two arcs (see [4] where the $\mathcal {NP}$-hardness of the hyperassignment problem which can be formulated as an integral min-cost hyperflow problem is proven).

In the remainder we only consider the uncapacitated minimum cost flow problem ($u\equiv \infty$) to make the presentation less technical and focus more on the underlying algorithmic ideas. However, the network simplex type algorithm described in the next section can also be adjusted to the capacitated case (details are deferred to a full version of the paper).

2 Min-Cost Hyperflow on Graph-Based Hypergraphs

In this section we characterize the basis matrices in the min-cost hyperflow problem on graph-based hypergraphs and show how most of the simplex operations can be done combinatorially. We do not specify any particular simplex rule, and leave any issues on the number of pivot iterations open for future research. Convergence can be guaranteed by usual methods.

In the remainder of this section let $H=(V,\mathcal A)$ be a hypergraph based on the directed graph $D=(V,A)$ and let $M\in \mathcal \{0,1,-1\}^{V\times \mathcal A}$ be its incidence matrix, i.e.,

$$\begin{aligned} M_{v,E}=\left\{ \begin{array}{rl} 1&{}\ v\in H(E)\\ -1&{}\ v\in T(E)\\ 0&{}\ v\notin H(E)\cup T(E) \end{array} \right. . \end{aligned}$$

(3)

With this definition, all inequalities of type (1) can be written as $Mf = b$. We assume without loss of generality that D is connected and $\{a\}\in \mathcal A$ for all $a\in A$. The column $M_{.E}$ corresponding to hyperarc $E=\{a_1,\ldots , a_k\}$ equals the sum of the columns $M_{.a_k}$. This implies that the rank of M is the same as the rank of the vertex-arc incidence matrix of D which is $|V|-1$ as D is connected.

In the following we will denote the submatrix of M restricted to the columns in some set $B\subseteq \mathcal A$ by $M_B$. For a set $B\subseteq \mathcal A$ we denote by $B_1=\{E\in B: |E|=1\}$ the set of all standard arcs and by $B_2:=B\setminus B_1$ the set of all “proper” hyperarcs. An easy observation shows that if B is a basis, then $D[\{a\in A: \{a\}\in B_1\}]$ is a forest having $|B_2|+1$ connected components, see for example [5]. If $B_2\ne \emptyset$ this condition is not sufficient. In this case, we choose a root $r\in V$ for each tree of the forest $D[\{a\in A: \{a\}\in B_1\}]$, denote this tree by $T_r$, and let R be the set of roots. We define a matrix $M_R\in \mathbb Z^{R\times B_2}$ by

$$\begin{aligned} M_R\left( r,E\right) = |V(T_r)\cap H(E)|-|V(T_r)\cap T(E)|. \end{aligned}$$

$M_R$ is independent of the concrete choice of the roots for the trees $T_r$. Furthermore, the columns of $M_R$ have the following useful property.

Theorem 1

Let B be a basis with $B_1$, $B_2$, R, $\{T_r\}_{r\in R}$ and $M_R$ as defined above. Given $E\in B_2$ there exists a unique function $f:B\rightarrow \mathbb R$ such that $f(E)=1$, $f(E')=0$ for all $E'\in B_2\setminus \{E\}$ and $f(\delta ^{in}(v)) = f(\delta ^{out}(v))$ for all $v\in V\setminus R$. Furthermore, the demand $f(\delta ^{in}(r))- f(\delta ^{out}(r))$ at a root vertex $r\in R$ is given by $M_{R}\left( r,E\right)$.

Proof

We first show that a function f with $f(E)=1$, $f(E')=0$ for all $E'\in B_2\setminus \{E\}$ and $f(\delta ^{in}(v)) = f(\delta ^{out}(v))$ for all $v\in V\setminus R$ exists. Therefore we set $b(v)=1$ for all $v\in T(E)$, $b(v)=-1$ for all $v\in H(e)$ and $b(r):=|V(T_r)\setminus \{r\}\cap H(E)|-|V(T_r)\setminus \{r\}\cap T(E)|$. With this definition we have $\sum _{v\in V(T_r)}b(v) = 0$ for all trees $T_r$ in particular $\sum _{v\in V}b(v) = 0$. This implies that there exists $f':\{a: \{a\}\in B_1\}\rightarrow \mathbb R$ such that $f'(\delta ^{in}(v))- f'(\delta ^{out}(v)) = b(v)$ for every $v\in V$. The uniqueness follows from the fact that $f'$ is uniquely determined on every tree $T_r$. Setting $f(\{a\}):=f'(\{a\})$ for all $\{a\}\in B_1$, $f(E)=1$, and $f(E')=0$ for all $E'\in B_2\setminus \{E\}$ gives a unique function satisfying the requirements of Theorem 1.

Now, we look at the demand induced by f on the roots. If $r\notin T(E)\cup H(E)$, then $f(\delta ^{in}(r))- f(\delta ^{out}(r)) = b(r) = M_R\left( r,E\right)$. If r is a head vertex of E, then $f(\delta ^{in}(r))- f(\delta ^{out}(r)) = b(r) + 1 = |V(T_r)\setminus \{r\}\cap H(E)|-|V(T_r)\setminus \{r\}\cap T(E)| + 1 = M_R\left( r,E\right) -1+1 = M_R\left( r,E\right) .$ The case $r\in T(E)$ is similar. $\qquad \square$

Theorem 1 shows that $M_R$ has the same properties as the matrix Cambini et al. [6] defined. In contrast to us, they used matrix operations and assumed that M has full rank which is not the case in our setting. The matrix $M_R$ enables us to characterize the basis matrices for the min-cost hyperflow problem.

Theorem 2

Let $B\subseteq \mathcal A$ be a subset of size $|V|-1$. $M_B$ is a basis matrix for the linear program defined by (1)–(2) if and only if

• (a) $D[{a\in A}: \{a\}\in B]$ is a forest with $|B_2|+1$ connected components.

• (b) $M_R$ has rank $|B_2|$.

Proof

Let $M_B$ be a basis matrix. (a) is easy to show. If (b) does not hold, then there exists a non-zero vector $y\in \mathbb R^{B_2}$ with $M_R\cdot y=0$. For every $E\in B_2$, let $f^E\in \mathbb R^B$ be a vector with the properties described in Theorem 1, and set $f=\sum _{E\in B_2}y(E)f^E$. For every $v\in V\setminus R$ we have

$$\begin{aligned} f(\delta ^{in}(v))- f(\delta ^{out}(v))= & {} \sum _{E\in B_2}y(E)\cdot \left( f^E(\delta ^{in}(v))- f^E(\delta ^{out}(v))\right) \\= & {} \sum _{E\in B_2}y(E)\cdot 0 = 0, \end{aligned}$$

and for $r\in R$ we get

$$\begin{aligned} f(\delta ^{in}(r))- f(\delta ^{out}(r))= & {} \sum _{E\in B_2}y(E)\cdot \left( f^E(\delta ^{in}(r))- f^E(\delta ^{out}(r))\right) \\= & {} \sum _{E\in B_2}y(E)\cdot M_R(r,E) = 0. \end{aligned}$$

Furthermore, $f^E(E) = 1$ and $f^{E'}(E)=0$ for all $E'\in B_2\setminus \{E\}$ imply that $f(E) = y(E)$ for all $E\in B_2$. Thus, f is a non-zero vector with $M_B\cdot f = 0$ which is impossible as the columns of $M_B$ are linearly independent.

Now, suppose (a) and (b) hold. The rows of $M_B$ sum to zero, thus its rank is at most |B|. By this fact and basic linear algebra, the rank of $M_B$ equals |B| if and only if for every $b\in \mathbb R^V$ with $\sum _{v\in V}b(v)=0$ the system $M_B\cdot f = b$ has a unique solution. By (a) we can find a flow $f'$ on B such that $f'(E)=0$ for all $E\in B_2$ and $f'(\delta ^{in}(v))- f'(\delta ^{out}(v)) = b(v)$ for all $v\in V\setminus R$. Next, we set $\delta (r):=b(r)-(f'(\delta ^{in}(r))- f'(\delta ^{out}(r)))$ for all $r\in R$ and solve $M_R\cdot y = \delta$. Again, let $f^E$ be the unique flow with the properties of Theorem 1. We set $f=\sum _{E\in B_2}y(E)f^E+f'$. For $v\in V\setminus R$ we have

$$\begin{aligned}&f(\delta ^{in}(v))- f(\delta ^{out}(v)) \\= & {} \sum _{E\in B_2}y(E)\cdot \left( f^E(\delta ^{in}(v))- f^E(\delta ^{out}(v))\right) + f'(\delta ^{in}(v))- f'(\delta ^{out}(v)) \\= & {} 0 + b(v), \end{aligned}$$

and for $r\in R$

$$\begin{aligned}&f(\delta ^{in}(r))- f(\delta ^{out}(r))\\= & {} \sum _{E\in B_2}y(E)\cdot \left( f^E(\delta ^{in}(r))- f^E(\delta ^{out}(r))\right) + f'(\delta ^{in}(r))- f'(\delta ^{out}(r))\\= & {} \sum _{E\in B_2}y(E)\cdot M_R(r,E) + b(r)-\delta (r)= b(r). \end{aligned}$$

This shows that $M_B\cdot f = b$ holds. The uniqueness follows from the fact that the function values at $B_2$ are uniquely determined by (b), and given the values on $B_2$ the function f on $B_1$ is uniquely determined by property (a). $\qquad \square$

Algorithm 1 describes a network simplex type algorithm for the min-cost hyperflow problem on graph-based hypergraphs. By our assumption, there exists a feasible min-cost hyperflow if and only if there exists a feasible flow on the underlying digraph. Our algorithm receives such a feasible flow together with the corresponding Basis B as an input.

In the remainder we show how to solve problems of the type $M_Bf = b$ (Primal) and $\pi ^T M_B = c^T_B$ (Dual) where $M_B$ is a basis matrix. We always assume that the trees $\{T_r\}_{r\in R}$ have its vertices and arcs ordered such that $v_1$ is the root, $v_{j}$ is a leaf in $T[\{v_1,\ldots , v_{j}\}]$ and $a_{j-1}$ is the arc $v_j$ is incident to. We start with the primal problem $M_Bf = b$ for which we basically use the algorithm described in the proof of Theorem 2. As a subroutine we need Algorithm 2 which given the demand $d_N$ on the non-root vertices $N:=V\setminus R$, and flow $f_2$ on the non-tree hyperarcs $B_2$ computes the unique flow $f_1$ on the tree arcs $B_1$ and demand $d_R$ on the roots R such that

$$M_B\cdot \left( \begin{array}{r} f_1\\ f_2 \end{array} \right) = \left( \begin{array}{r} d_N\\ d_R \end{array} \right) $$

where the rows and columns of $M_B$ are arranged accordingly.

Using the algorithm above we can solve $M_Bf=b$ as follows:

• 1. Compute Flow$(B, \{T_r\}_{r\in R}, b_N,0)$.

• 2. Solve $M_R\cdot y = (b_R-d_R)$.

• 3. Compute Flow$(B, \{T_r\}_{r\in R}, b_N,y)$.

In the first step we compute a flow with value zero on all hyperarcs $E\in B_2$ which induces the right demands on the non-root vertices. In the second step we calculate the flow needed on $B_2$ to correct the demand at the root vertices, and finally in step 3 we adjust the flow on the tree arcs.

For the dual problem $\pi ^T M_B = c^T_B$ we need Algorithm 3 as a subroutine. Given the cost $c_1$ of all tree arcs $B_1$, and the potential $\pi _R$ at the root vertices it computes a cost vector $e_2$ on $B_2$ and potential $\pi _N$ on the non-root vertices such that $(\pi _N^T, \pi _R^T)M_B = (c_1^T, e_2^T),$ i.e., the reduced cost of every basic hyperarc is zero.

As the rank of $M_B$ is $|V|-1$ the system $\pi ^T M_B = c^T_B$ has no unique solution. Thus, we can fix the value of one vertex, for example we can choose one of the roots $r_1\in R$ and set $\pi (r_1)=0$.

Now, we can solve Dual as follows.

• 1. Compute Potential$(B, \{T_r\}_{r\in R}, c_1,0)$.

• 2. Find a solution to $y^T M_R = (c_2^T-e^T_2)$ with $y(r_1)=0$.

• 3. For all $r\in R$ set $\pi (r)\leftarrow y(r)$ and $\pi (v)\leftarrow \pi (v)+\pi (r)$ for all $v\in V(T_r)$

First, the potential on the roots is set to zero, and we compute a potential on the non-root vertices such that the reduced cost of every tree arc is zero. In the second step the correct potential of the root vertices is calculated, and in step 3 the potential on the non-roots is adjusted. In contrast to the primal problem, we do not have to call Algorithm 3 a second time. It suffices to add the potential of the root vertex to the potential of the other vertices in the tree.