Minimum Cost Flow Problem

The minimum cost flow problem is related to many real world applications such as finding Wardrop equilibria in traffic networks.

Consider a strongly connected graph \(G = (V, E)\) without self loops and parallel edges. We denote \(n = |V|\) the number of vertices or nodes and \(m = |E|\) the number of links or edges. We want to find a flow \(\mathbf{x}\) – a vector of shape (m, ) – that minimizes some objective cost function \(C\):

\[\begin{split}\begin{align*} \min \text { } & C(\mathbf{x}) \\ \text {s.t.} \quad \mathbf{\Gamma} \mathbf{x} &= \mathbf{b}, \\ \mathbf{x} &\geq \mathbf{0}, \end{align*}\end{split}\]

where show definitions:

  • \(\mathbf{\Gamma}\) is the incidence matrix of \(G\) and

  • \(\mathbf{b}\) a demand vector of shape (n, ) that encodes the demand values for each node, negative values representing sources.

Given a demand \(\mathbf{b}\), many flows \(\tilde{\mathbf{x}} \in \mathcal{X}\) are feasible solutions. The minimum cost flow has lower cost compared to all other feasible flows: \(C(\mathbf{x}) \leq C(\tilde{\mathbf{x}})\).

1. Undirected minimum cost flow problem

The classic minimum cost flow restricts quantities to traverse edges in one direction only. However, in many applications – physical networks such as gas, electrical or water networks – units may flow along the same edge in different directions. Solving the above optimization problem without the restriction \(\mathbf{x} > 0\) thus yields the undirected minimum cost flow:

\[\begin{split}\begin{align*} \min \text { } & C(\mathbf{x}) \\ \text {s.t.} \quad \mathbf{\Gamma} \mathbf{x} &= \mathbf{b}. \end{align*}\end{split}\]

2. Multi-commodity minimum cost flow problem

Consider a \(n \times k\) demand matrix \(\mathbf{B}\) where each column represents a demand vector. Here, we want to find a \(n \times k\) flow matrix \(\mathbf{X}\), where each column \(\mathbf{X}_{:j}\) is the minimum cost flow associated with the demand vector \(\mathbf{B}_{:j}\). A minimum cost flow matrix is the solution to the following optimization problem:

\[\begin{split}\begin{align*} \min \text { } & C(\mathbf{X}) \\ \text {s.t.} \quad \mathbf{\Gamma} \mathbf{X} &= \mathbf{B}, \\ \mathbf{X} &\geq \mathbf{0} \end{align*}\end{split}\]

3. Characterization of minimum cost flows

3.1 Optimal potentials

A vector \(\mathbf{x} \in \mathbb{R}^m\) is a minimum cost flow that solves the above optimization problem iff there is a vector \(\mathbf{\pi} \in \mathbb{R}^n\) of vertex potentials so that:

\[\begin{split}\begin{aligned} f_{e}^{-}\left(x_{e}\right) \leq \pi_{w}-\pi_{v} & \leq f_{e}^{+}\left(x_{e}\right) \text { for all } e=(v, w) \in E \text { with } x_{e}>0, \\ \pi_{w}-\pi_{v} & \leq f_{e}^{+}\left(x_{e}\right) \text { for all } e=(v, w) \in E \text { with } x_{e}=0 , \end{aligned}\end{split}\]

where show definitions:

  • \(f_e\) is piecewise linear marginal cost function,

  • \(f_{e}^{-}\left(x_{e}\right)\) denotes the left-hand limit of \(f_e\), and

  • \(f_{e}^{-}\left(x_{e}\right)\) the right-hand limit of \(f_e\).

The vector \(\mathbf{\pi}\) is then termed optimal potential (vector). Optimal potentials can thus be used to verify if a flow \(\mathbf{x}\) is indeed a minimum cost flow. If we can compute an optimal potential, \(\mathbf{x}\) is a minimum cost flow; if no such potential exsits, it is not.

Potentials and direction of flow

Due to our convention for demand vectors \(\mathbf{b}\) to encode sources with negative values and sinks with positive values, we define the potential difference \(\pi_w - \pi_v\), i.e., the potential increases in the direction of flow. This may not be intuitive for physical applications where quantities usually “flow” from higher to lower potential.