Parametric Minimum Cost Flows

There exists a variety of solutions to the minimum cost flow problem. paminco provides solutions to a slighly different problem.

1. Minimum cost flow functions

The goal is to find a minimum cost flow function that maps a demand factor $\lambda$ to a minimum cost flow:

$$\begin{array}{r}\begin{array}{rl}min& C(\mathbf{x})\\ \text{s.t.}\mathbf{\Gamma }\mathbf{x}& =\mathbf{h}(\lambda ),\\ \mathbf{x}& \ge \mathbf{0},\end{array}\end{array}$$

where show definitions:

• $\mathbf{\Gamma }$ is the incidence matrix and

• $\mathbf{h}(\lambda ):\mathbb{R}\to {\mathbf{b}}_{\lambda }$ a demand function.

For notational simplicity, we only discuss linear demand functions $\mathbf{h}(\lambda )=\lambda \mathbf{b}$.

1.1 Alpha-beta-approximate minimum cost flow functions

It may not always be (computationally) feasible to compute an exact minimum cost flow function and the function has to be approximated.

Consider an interval $[0,{\lambda }^{max}]$, for which we want to find an $(\alpha ,\beta )$-approximate minimum cost flow function. A function is an $(\alpha ,\beta )$-approximate minimum cost flow function if the cost of the flow $\mathbf{x}(\lambda )$ exceed the optimal cost at most by a relative factor of $\alpha$ and an absolute error of $\beta$:

$$\tilde{C}(\lambda )\le \alpha C(\lambda )+\beta \text{ for all }\lambda \in [0,{\lambda }^{max}],$$

where $\tilde{C}(\lambda )=\tilde{C}(\mathbf{x}(\lambda ))=\sum _{e\in E}{F}_e(x_e(\lambda ))$ denotes the cost of the flow $\mathbf{x}(\lambda )$.

2. Parametric electrial flows

Instead of computing a minimum cost flow $\mathbf{x}$ (for a fixed demand) directly, we can compute an optimal potential $\pi$ which induces a flow:

$$\mathbf{x}={\mathbf{f}}^{-1}({\mathbf{\Gamma }}^T\pi ),$$

where ${\mathbf{f}}^{-1}$ maps an optimal potential to an electrial flow:

$${\mathbf{f}}^{-1}:\mathrm{\Pi }\to {\mathbb{R}}^m\pi \to {\mathbf{f}}^{-1}(\pi ):=(f_e^{-1}({\pi }_w-{\pi }_v){)}_{e\in E}.$$

2.1 Linear marginal cost

Assume that the marginal cost for all edges are linear and of the following form: $f_e(x)=2ax+b$. Then we find a linear function $\pi (\lambda )$ and its induced linear electrical flow $\mathbf{x}(\lambda )$:

$$\begin{array}{r}\begin{array}{rl}\pi (\lambda )& ={\mathbf{L}}^{\ast }(\lambda \mathbf{b}+\mathbf{\Gamma }\mathbf{d})\text{and}\\ \mathbf{x}(\lambda )& =\mathbf{C}{\mathbf{\Gamma }}^T\pi (\lambda )-\mathbf{d}=\mathbf{C}{\mathbf{\Gamma }}^T{\mathbf{L}}^{\ast }(\lambda \mathbf{b}+\mathbf{\Gamma }\mathbf{d})-\mathbf{d},\end{array}\end{array}$$

where show definitions:

• $\mathbf{C}=\text{diag}(1/2a_1,1/2a_2,...,1/2a_m)$,

• $\mathbf{d}=(b_1/2a_1,b_2/2a_2,...,b_m/2a_m{)}^T$,

• $\mathbf{L}=\mathbf{\Gamma }\mathbf{C}{\mathbf{\Gamma }}^T$ the weighted Laplacian of the graph, and

• ${\mathbf{L}}^{\ast }$ the generalized inverse of $\mathbf{L}$.

At a glance

Linear marginal cost result in a linear minimum cost flow function.

Example: linear resistances show / hide

Consider an electrical network with linear resistances, i.e., $f_e(x)=r_e\cdot x$. The objective function simplifies to $C(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T\mathbf{R}\mathbf{x}$ with $\mathbf{R}=\text{diag}(r_{e_1},r_{e_e},...,r_{e_m})$.

Then we find the optimal potential and minimum cost flow as:

$$\begin{array}{r}\begin{array}{rl}\pi (\lambda )& ={\mathbf{L}}^{\ast }\mathbf{h}(\lambda )\\ \mathbf{x}(\lambda )& =\mathbf{C}{\mathbf{\Gamma }}^T{\mathbf{L}}^{\ast }\mathbf{h}(\lambda ),\end{array}\end{array}$$

where $\mathbf{C}={\mathbf{R}}^{-1}$.

Thus, the parametric electrial flow is just a linear transformation of the demand function $\mathbf{h}(\lambda )$.

2.2 Piecewise linear marginal costs

The assumption of linear marginal cost restricts the applicability of the algorithm. We now discuss problems with piecewise linear marginal costs:

Graph

Regions in $\mathrm{\Pi }$ and solution curve

Induced edge flows

The piecewise linear marginal edge cost subdivide the potential space $\mathrm{\Pi }$ into regions. We denote $\mathbf{t}=(t_{e_1},t_{e_2},...,t_{e_m}{)}^T$ the vector of the indices per edge cost function. Given an optimal potential $\pi$, the electrical flow is then:

$$\mathbf{x}={\mathbf{C}}_{\mathbf{t}}{\mathbf{\Gamma }}^T\pi -{\mathbf{d}}_{\mathbf{t}}={\mathbf{C}}_{\mathbf{t}}{\mathbf{\Gamma }}^T{\mathbf{L}}_{\mathbf{t}}^{\ast }(\mathbf{b}+\mathbf{\Gamma }{\mathbf{d}}_{\mathbf{t}})-{\mathbf{d}}_{\mathbf{t}}$$

In a region $R_{\mathbf{t}}$ the solution curve is linear. The full solution curve is union of the solution segments ${\mathrm{\Pi }}_{\mathbf{t}}$ and thus a piecewise linear function:

$$\pi \left({\mathbb{R}}_{\ge 0}\right):=\{\pi (\lambda )\mid \lambda \ge 0\}=\bigcup _{t\in \overline{T}}{\mathrm{\Pi }}_t.$$

Furhter, for all regions, there exist numbers ${\lambda }_t^{\text{min}}$ and ${\lambda }_t^{\text{max}}$:

$${\mathrm{\Pi }}_{\mathbf{t}}=\{{\pi }_{\mathbf{t}}+\lambda \mathrm{\Delta }{\pi }_{\mathbf{t}}\mid \lambda \in [{\lambda }_t^{\text{min}},{\lambda }_t^{\text{max}}]\}.$$

Hence, the main challenge lies in finding the correct regions $R_{\mathbf{t}}$. The Electrial Flow Algorithm (EFA) [WK21] provides a solution for this problem.

Idea behind the Electrial Flow Algorithm

Piecewise linear marginal cost result in a subdivision of the potential space $\mathrm{\Pi }$. For every region $R_{\mathbf{t}}\in \mathrm{\Pi }$, the solution curve is linear. Thus the full solution curve is piecewise linear. The difficulty thus lies in finding the correct sequence of regions.

2.3 Interpolation of cost functions

The EFA algorithm is restricted to piecewise linear marginal cost functions $f_e$ and thus minimum cost flow problems with piecewise quadratic cost functions. However, it is possible to approximate continous convex cost functions $F_e$ with piecewise quadratic convex cost functions ${\tilde{F}}_e$ [Roc84]. The Marginal Cost Approximation (MCA) algorithm builds on that idea and “feeds” the EFA with approximated piecewise linear marginal cost. Hence, MCA calculates an alpha-beta-approximate minimum cost flow function.

See also

MCAInterpolationRule : Criteria for proper approximation of cost functions.

References

WK21

Klimm M, Warode P (2021) “Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs.” Mathematics of Operations Research. Available at https://www3.math.tu-berlin.de/disco/research/publications/pdf/KlimmWarode2021.pdf

Roc84

Rockafellar, RT (1984) Network Flows and Monotropic Optimization (John Wiley and Sons, Hoboken, NJ)