CO351

Introduction

Network Flow Theory: Class of optimization problems on graphs (directed graphs), usually involving the movement of stuff.

Example: Transshipment problem.

Directed graph. Nodes weights are the supply or demand, arc weights are the cost to move one good across the arc. We want to move all goods from supply to demand while minimizing total cost.

Solutions are representing using another digraph with arcs representing the amount of goods transfered between nodes.

Graphs

Definitions

• G = (V, E) consists of a set of vertices V and unordered pairs of vertices E.
• Degree of a vertex v is the number of edges incident to v, d_G(v) or d(v).
• Walk is sequence of vertices v_1, ..., v_k where v_i v_{i+1} are edges.
• Path is a walk with distinct vertices.
• Cycle is a walk v_1, ..., v_k, v_1, where v_1, ..., v_k are distinct and k \ge 3.

Connectivity and cuts

• G is connected if there is a path between every pair of vertices, disconnected otherwise.
• For S \subseteq V, the cut induced by S is the set of all edges with exactly one edge in S.
• If s, t \in V, s \in S, v \not\in S, then \delta(S) is an s,t-cut.
• There exists an s,t-path if and only if every s,t-cut is non-empty.

Trees.

• Connected graph with no cycles. n vertices with n - 1 edges.
• Spanning tree of G is a subgraph that is a tree which uses all vertices of G.
• G has a spanning tree if and only if G is connected.
• If T is a tree and u, v are not adjacent, T + uv contains exactly only cycle C. If xy is an edge of C then T + uv - xy is another tree.

Directed Graphs

Definitions

• Directed graphs (digraph) D = (N, A) is a set of nodes N and a set of arcs A that are ordered pairs of nods.
• For an arc uv, u is the tail, v is the head.
• Out-degree of v is the number of arcs whose tail is v, d(v).
• In-degree of v is the number of arcs whose head is v, d(\overline{v}).
• Directed walk (diwalk) is a sequence of nodes v_1, ..., v_k such that v_i v_{i+1} arr arcs.
• Directed path (dipath) is a diwalk where all nodes are distinct.
• Directed cycle (dicycle) is a diwalk v_1, ..., v_k, v_1 where v_1, ..., v_k are distinct and k \ge 3.

Cuts

For S \subseteq N, the cut induced by S is the set of all arcs whose tails are in S and heads are not in S. \delta(S) = \{uv \in A: u \in S, v \not\in S\}. \delta(\overline{S}) = \{uv \in A, u \not\in S, v \in S\}.

• If s, t \in N, where s \in S and t \not\in S, then \delta(S) is an s,t-cut.

Proposition: There exists an s,t-dipath if and only if every s,t-cut is non-empty.

(\Rightarrow) Let s = v_1,v_2,...,v_k=t be a s,t-dipath. Let \delta(S) be an s,t-cut. Since v_1 \in S, v_k \not\in S, there exists a largest index i < k such that v_i \in S, v_{i+1} \not\in S. So v_i v_{i+1} \in \delta(S), so \delta(S) is non-empty.

(\Leftarrow) Assume every s,t-cut is non-empty. Let S be the set of all nodes v such that an s,v-dipath exists. If t \in S, then an s,t-dipath exists, and we are done. If t \not\in S, then \delta(S) \neq \emptyset, so there must exist some arc uv \in \delta(S). Since u \in S, there exists a u,v-dipath P. Then P + uv is an s,v-dipath so v \in S, contradiction.

Underlying Graph

Remove the directions on the arcs to get edges.

• Digraph is connected if its underlying graph is connected. Note: Might not have a dipath between certain ordered pairs of nodes.
• Spanning tree is a spanning tree of the underlying graph.
• Cycle is a cycle in the underlying graph. Note: Not necessarily a directed cycle.
  • When considering the direction of a cycle in the underlying graph, arcs that go along the direction are forward arcs, arcs ones that go against are backward arcs.

Transshipment Problem (TP)

1. Digraph D = (N, A).
2. Node demands b_v for each v \in N. Negative demand corresponds to supply.
3. Arc costs w_e for each e \in A.

A solution is called a flow. The goal is to minimize the total cost of the flow.

LP Formulation

Notation: If x \in \mathbb{R}^T and S \subseteq T, then x(S) = \sum_{i \in S}x_i.

1. Variables. For each arc e \in A, define x_e \in \mathbb{R}.
2. Objective function. Cost of transporting x_e on arc e is w_e x_e. Want to minimize total costs. \min w^T x.
3. Constraint. Inflow minus outgoing flow equals the demand. \delta(u) - \delta(\overline{u}) = b_u. All variables are non-negative, x_e \ge 0.

\begin{aligned} \min\ &w^Tx \\ \text{s.t } &x(\delta(\overline{v})) - x(\delta(v)) = b_v,\ \forall v \in N \\ &x \ge 0 \end{aligned}

Matrix form is called an incidence matrix where the rows represent nodes and the columns represent arcs.

Dual LP for TP

\begin{aligned} \min\ &w^T x \\ \text{s.t. } &x(\delta(\overline{v})) - x(\delta(v)) = b_v,\ &\forall v \in N \\ x \ge \mathbf{0} \end{aligned}

• When we take the dual there will be a variable for every node, and a constraint for every arc in the original digraph.

\begin{aligned} \max\ &b^T y \\ \text{s.t. } &y_v - y_u \le w_{uv}\ \forall uv \in A \end{aligned}

CS Conditions

Recall: Variable is zero or the corresponding constraint is tight.

• The primal constraints are always tight.

x_{uv} = 0 or y_v - y_u = w_{uv}, \forall uv \in A. So x_{uv} > 0 implies y_v - y_u = w_{uv}.

Recall: Let (P), (D) be a primal-dual pair. Then x, y are optimal solutions to (P), (D) if and only if they are feasible and satisfy CS conditions.

Given a feasible solution to (P), how do we generate a feasible solution to (D)?

Arbitrarily assign the value of a node to be 0, then use the arc constraints to fill in the other nodes. So we have a feasible x and x,y satisfy CS conditions. It remains to show that y is feasible.

We need to check arc conditions not included in the solution.

Alternatively, given that x, y are feasible, use strong duality.

Basic Feasible Solution for TP

Recall: Basis is a set of linearly independent column that form a square invertible matrix. Every basis corresponds to a unique basic solution.

Consider the incidence matrix of a digraph. The rows are linearly independent, because every column will sum to zero. So the rank of the matrix is at most |N|-1.

We assume that the coefficient matrix has full row rank in simplex. So we row reduce to get an equivalent system with full row rank.

What is the rank of the incidence matrix of a digraph D(N, A)?

There are |N| rows, rows are dependent, so the rank is at most |N| - 1. Every column represents an arc, so we can ask which arcs can we pick so the corresponding columns form a basis.

Consider any undirected cycle in the digraph. This corresponds to a square matrix with dependent columns.

Proposition: If a set of arcs does not contain a cycle, then the columns of the incidence matrix corresponding to the arcs are linearly independent.

Suppose these columns are not independent. Let us consider the set of columns with non-zero coefficients. So for any row, we have either all entries zero or at least two non-zero. Let us collect all these arcs and the nodes with at least 2 non-zero entries. We have a digraph where every node is incident with at least 2 arcs. So this digraph must have a cycle.

So to find independent columns, we find arcs that don’t have cycles. To find a basis, we need as many arcs as possible. For any connected digraph, a spanning tree exists with |N| - 1 arcs, corresponding to |N| - 1 independent columns. So the rank is at least |N| - 1, but the rank is at most |N| - 1. So the rank is equal to |N| - 1 and we have a basis.

Theorem: Let M be the incidence matrix of a connected digraph D = (N, A). Then the rank of M is |N| - 1. Moreover, a set of |N| - 1 columns of M is a basis if and only if the |N| - 1 arcs corresponding to these columns is a spanning tree of D.

Exercise: Determine the rank for a disconnected digraph.

Basic Solution

• Start with our spanning tree as the basis.
• Arcs not in the spanning tree will be zero because they are non-basic variables.
• Starting at a leaf, we iteratively solve for x using the flow constraints.
• If the end result is a feasible flow, then it is a basic feasible solution (BFS).

Primal-Dual Relations in Simplex

Consider a state of the simplex algorithm.

1. Suppose we have some coefficients in the objective vector equal to zero (canonical form). What does this mean for the corresponding dual?

   The dual constraint is tight for the basic variables. Non-basic variables have value 0.

   So the CS conditions are satisfied.

2. Suppose a coefficient is positive, what does this mean for the corresponding dual?

   The dual constraint is not satisfied. We are “trying to fix” that constraint in the step of the simplex algorithm.

3. We stop when all constriants are non-positive, what does this mean for the corresponding dual?

   All dual constraints are satisfied, y is feasible.

So we see that the simplex keeps x feasible, with CS conditions satisfied, and works towards the feasibility of y. When y becomes feasible, we have optimal solutions.

Application to TP

• For the dual, we add a slack variable so that it is an equality constraint. -y_u + y_v + \overline{w_{uv}} = w_{uv}, \forall uv \in A, \overline{w} \ge \mathbf{0}.

  • \overline{w_{uv}} for arcs in the tree are zero since they are the tight constriants.
  • Negative values imply that the dual constraints are not satisfied, so they are the entering variable.

Definition: A vector y \in \mathbb{R}^N is called a node potential. Given y, the reduced cost of arc uv is \overline{w_{uv}} = y_u + w_{uv} - y_v. A node potential is feasible if \overline{w_{uv}} \ge 0, \forall uv \in A.

Exercise: How do we find a “leaving arc”? Add flow to the entering arc, adjust flow on basic arcs while maintaining feasibility.