This work by Anthony Zhang is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright 2013-2017 Anthony Zhang.
Network Flow Theory.
Martin Pei
Section 001
Email: mpei@uwaterloo.ca
Office Hours: Mondays/Tuesdays 4pm-5pm in MC 6492
Mondays/Wednesdays/Fridays 1:30pm-2:20pm9 assignments, due on wednesdays, lowest assignment mark is dropped, submitted via Crowdmark. Assignment 0 is worth a bonus 1%.
Network theory deals with modelling problems using directed graphs, extending CS239. Network flow theory deals with flow problems over these directed graphs. A typical problem: given so-and-so network of roads (directed graph), each with different widths (cost of taking a road), how much traffic can we route from point A to B? Essentially, we're extending linear programming concepts from CO250 to directed graphs.
Real examples of networks: water pipes, electrical grid, and road networks.
Graph theory review: a graph is a pair of a set of vertices (arbitrary objects) and a set of edges, which are unordered pairs of vertices. The degree of a vertex is the number of edges incident to it, denoted d_G(v). A walk is a sequence of vertices in a graph where consecutive vertices are edges in the graph. A path is a walk with no repeated vertices or edges. A graph is connected if and only if there is a path between any two vertices. A cycle is a walk where the last vertex is the same as the first vertex. A cut induced by a set of vertices S is the set of edges with one end in S and another end not in S, denoted \delta(S). The size of a cut is denoted d(S) or \abs{\delta(S)}. A tree is a connected acyclic graph.
Theorem: there's an s, t-path in G if and only if for all X \subseteq V(G) such that s \in X, t \notin X, \delta(X) \ne \emptyset - exactly when every subset of vertices including s but not t has a non-empty cut.
Proof:
First we'll prove the forward direction. Assume an s, t-path exists. Let v_0, \ldots, v_k be one of those s, t-paths, let X \subseteq V(G) be an arbitrary subset of graph vertices such that s \in X, t \notin X.
Let i be the smallest index in the s, t-path such that v_i \notin X. Since it's the smallest index, v_{i - 1} must be in X, so v_{i - 1} v_i \in \delta(X), so \delta(X) is non-empty, as required.
Now for the opposite direction. Assume no s, t-path exists. Then s and t are in two different components A and B, since otherwise the path would exist.
Clearly, the cut induced by A must be empty, since if it isn't, then any vertex in the edges of the cut that weren't in A should be in A.
Let T be a tree. Then \abs{E(T)} = \abs{V(T)} - 1. Also, a unique path exists between any two vertices, and adding any edge that doesn't already exist to T will form exactly one cycle, Removing any edge from that resulting cycle gives us a tree again.
Directed graphs (digraphs) are very similar to graphs. A digraph D = \tup{N, A} is a pair of a set of nodes (arbitrary objects) and a set of arcs, which are ordered pairs of nodes. Each node has an in-degree (number of arcs that point to it) denoted d(\overline v) or d^-(v), and an out-degree (number of args that point from it) denoted d(v) or d^+(v). A diwalk is a sequence of nodes such that consecutive nodes have arcs between them, a dipath is a directed walk with no duplicated nodes or arcs, and a dicycle is a dipath such that the first and last nodes are the same.
Directed graphs can have cycles of length 2, unlike undirected graphs. A directed graph is acyclic if there are no dicycles. We can also talk about cycles in a directed graph, which are simply the cycles if we ignore directions in the graph.
If every node of a digraph has out-degree of at least 1, the digraph must have a directed cycle. Proof: let v_0, \ldots, v_k be the longest dipath in the digraph. Clearly, v_k has out-degree at least 1, so it has an arc pointing to another node u. Clearly, u must be in the dipath, since if it wasn't then the path could be strictly longer, which isn't possible since the dipath is already the longest. So u must be in the dipath, and this forms a directed cycle in the digraph.
Likewise for an undirected graphs, if every vertex has degree at least 2, there must be an undirected cycle. We can prove this in a very similar way.
A digraph is connected exactly when its corresponding undirected graph is connected - if every vertex in the underlying graph has a path to every other, ignoring direction. A digraph is strongly connected exactly when every node has a directed path to every other node.
For any subset of notes S \subseteq N, the cut induced by S is the set \delta(S) = \set{xy \in A \middle| x \in S, y \notin S} - the set of arcs that go outward from S. There's also \delta(\overline S), which is the set of arcs that go inward toward S (the cut induced by the complement).
Just like for an undirected graph, an s, t-dipath exists if and only if every s, t-cut is non-empty. The proof is very similar to the version for undirected graphs.
Suppose we have a network consisting of a digraph, and some objects called supplies/goods present at various nodes (nodes are labelled with the net quantity demanded). We want to transport goods from where there's a negative net quantity demanded to where there's a positive net quantity demanded. The quantity we transport along the arcs is the flow. In other words, a flow is a weighting for each arc in a digraph, representing how much of a quantity we're transporting along that arc.
The inflow of a node is the sum of the weights of the arcs going into the node. The outflow of a node the sum of the weights of the arcs leaving the node. Inflow minus outflow is the weight of the vertex - the net quantity demanded.
There are also costs associated with letting goods flow through an arc. A cost is a edge weighting, just like a flow, but the weight of an edge represents the cost of transporting one unit of a good through that arc.
The goal of the problem is to find a flow such that the net quantity demanded becomes non-positive, such that we minimize the cost of that flow.
New notation: \vec o \in \mb{R}^S, where S is a set, means that o is a vector with \magn{S} elements, each one representing an element s of S. Additionally, we can write the element corresponding to s as o_s.
Formally: suppose we have a digraph D = \tup{N, A}, a node weighting \vec b \in \mb{R}^N (the net quantity demanded of the good at each node in N), and an arc weighting \vec w \in \mb{R}^A (the cost of transporting a unit of the good through each arc in A). A flow is an arc weighting \vec x \in \mb{R}^A such that \vec x \ge \vec 0 and \sum_{iv \in A} x_{iv} - \sum_{vj \in A} x_{vj} = b_v for all v \in N (total inflow minus total outflow is equal to b_v for any v \in N). The problem is to minimize \sum_{ij \in A} w_{ij} x_{ij}.
Intuitively, a flow problem on a digraph tries to move positive quantities of goods along arcs from nodes that are negative to nodes that are positive.
If b_v is positive for a node v, then v is a supply node. If it's negative, v is a demand node.
New notation: if N \subseteq S, then o(N) = \sum_{v \in N} o_v. In other words, if we call a vector like a function with a set of indices, we get back the sum of the elements at those indices.
Therefore, \sum_{iv \in A} x_{iv} - \sum_{vj \in A} x_{vj} = b_v$ is equivalent to x(\delta(\overline v)) - x(\delta(v)) = b_v for all v \in N.
Additional assumptions for network flow problems in this course:
The transshipment problem can be solved simply using linear programming. The general form of the LP is: "minimize \sum_{ij \in A} w_{ij} x_{ij} subject to \sum_{iv \in A} x_{iv} - \sum_{vj \in A} x_{vj} = b_v for all v \in N, \vec x \ge \vec 0" (the values of \vec w and \vec b are fixed). In other words, we're minimizing the total cost of performing the shipments such that we still manage to make inflow minus outflow equal to the net quantity demanded for each individual node.
In matrix form, the columns are indexed by arcs, and the rows are indexed by nodes. At a given row a and column ab within the matrix, we put a 0 when there's no such arc, 1 if the digraph contains the arc ba, and -1 if the digraph contains the arc ab.
Formally, an incidence matrix for a digraph D = \tup{N, A} is an \abs{N} by \abs{A} matrix M where M_{v, ij} = \begin{cases} -1 &\text{if } v = i \\ 1 &\text{if } v = j \\ 0 &\text{otherwise} \end{cases}. As it turns out, the matrix form of the LP for the transshipment problem will always have a coefficients matrix that is the incidence matrix of the digraph, under the assumptions we make for this course.
Therefore, we can write the LP more simply as "minimize \vec w \cdot \vec x subject to M \vec x = \vec b, \vec x \ge \vec 0", where M is the incidence matrix for the digraph, \vec w is the costs for each arc, \vec b is the net quantity demanded in each vertex, and \vec x is the amount of goods to send along each edge.
Interestingly, since in an incidence matrix, every column of M has exactly one 1 and one -1, or is all 0. Therefore, the sum of all the rows in the matrix gives \vec 0. If we sum the A \vec x = \vec b, we get b(N) = 0 - our assumption that the total net quantity demanded is 0.
Consider now the dual for the LP: "minimize \vec b \cdot \vec y subject to M^T \le \vec c for all ij \in A, \vec y free", where M is the incidence matrix for the digraph. We can then use complementary slackness to show that the LP is optimal.
Assignment 1 is out, due on Wednesday.
New notation: M_a is the column in M corresponding to the arc a.
New notation: \overtilde M is M with the last row removed.
Summary of transshipment problem (TP): minimize \vec w^T \vec x subject to M \vec x = \vec b and \vec x \ge \vec 0. Here, \vec w is the costs, \vec b is the demands, and M is the indcidence matrix. The M \vec x = \vec b is called the flow constraint, while the \vec x \ge \vec 0 is the non-negativity constraint.
To start solving a TP instance with Simplex, we need to find a feasible basis. However, note that the rows of the incidence matrix M are not linearly independent, since when you sum up all the rows, you get \vec 0 - the rank of the n by m incidence matrix is n - 1. ;wip: why can't it be less than n - 1? add proof
To get around this, we ignore one row, so we pretend the matrix is n - 1 by m, and pick n - 1 columns for a basis instead. We usually can do this by inspection, or the auxilary problem method.
In fact, the columns of M that correspond to the edges of any undirected cycle are linearly dependent, and those that do not are linearly independent. Proof: for any undirected arc v_1, \ldots, v_k, v_1 in a digraph, v_i v_{i + 1} is a forward arc, whereas v_{i + 1} v_i is a backward/reverse arc. Let F be the set of forward arcs in the undirected cycle, and R the reverse arcs. Clearly, \sum_{a \in F} M_a - \sum_{a \in R} M_a has the same sum as if the undirected cycle was a dicycle instead. Clearly, the sum of the arcs in a dicycle is 0, since for the dicycle each row will have exactly one -1 and one 1 entry (one incoming arc and one outgoing arc) \sum_{a \in F} M_a - \sum_{a \in R} M_a = 0. We've now found k columns that are linearly dependent, since they sum to 0.
Likewise, a set of linearly dependent columns must contain an undirected cycle (proof left as exercise). So there exists a set of linearly dependent columns if and only if the arcs corresponding to the columns in that set form an undirected cycle.
So to find a basis (ignoring one row) of \overtilde M, we need to find a set of n - 1 linearly independent arcs - so by the above proof, a set of n - 1 arcs that don't have any cycles. From graph theory, this must be a spanning tree by definition, since it has no cycles and contains n vertices - a set of columns of an incidence matrix M is a basis for M if and only if the arcs corresponding to those columns forms a spanning tree of the digraph. Note that spanning trees ignore arc direction, as if we're working on an undirected graph.
To find a basic solution corresponding to some spanning tree, we can start from the leaves (vertices in the spanning tree of degree 1) and work our way up to the root - a leaf node of value -10 must have 10 flow coming out of it, since it must end up with 0 value in the end, for example. This isn't necessarily a basic feasible solution, because it might not satisfy the non-negativity constraint - some of the flow directions might be different from the arc directions, like if we have a negative valued node and in the spanning tree, it's incident to an inward pointing arc. If we get an infeasible solution, we can just keep trying other spanning trees until we find a feasible one.
Review of simplex method. In the simplex method, at all times we maintain a basic feasible solution for the LP, and a solution for the dual that satisfies all constraints (except the non-negativity constraints), and the complementary slackness conditions. Each step fixes some of the non-negativity constraints, so eventually both dual and primal solutions are satisfied, and by the complementary slackness theorem, both solutions must be optimal.
Recall the transshipment problem LP: "minimize \vec w \cdot \vec x subject to M \vec x = \vec b and \vec x \ge \vec 0", as well as its dual, "maximize \vec b \cdot \vec y subject to -y_a + y_b \le w_{ab} for all ab \in A and \vec y free". The vector \vec y is knows is the node potential.
To start solving this using simplex, we start by adding a slack variable to each dual inequality: "maximize \vec b \cdot \vec y subject to -y_a + y_b + \overline{w}_{ab} = w_{ab} for all ab \in A and \vec y free and \vec{\overline{w}} \ge \vec 0". Here, the \overline{w}_{ab} = w_{ab} + y_i - y_j is called the reduced cost of the arc ab.
A node potential \vec y is a feasible node potential if and only if the non-negativity constraints are satisfied for \overline{w}_{ab} for all b A$ - when all the slack variables are non-negative. By complementary slackness, if x_{ab} > 0, then \overline{w}_{ab} = 0 in the dual LP. $a When we're using the simplex method, we start off with a basic feasible solution. This gives us a spanning tree over the digraph, and we then choose an entering arc and a leaving arc. Adding the entering arc forms a cycle, and removing the leaving arc breaks it again.
;wip: missed, but was about network simplex algo
Finishing off the network simplex example we went through last time.
By the fundamental theorem of linear programming, a linear program is always unbounded, infeasible, or has an optimal solution.
What do the dual potentials \vec y for nodes mean? Well, we might think of each value of \vec y as the relative price of buying the good at that node - if \vec y_a = 0 and there's an arc of cost 30 to node b, then \vec y_b = 30. Likewise, if there's then an arc of cost 50 from b to c in our spanning tree, then \vec y_c = 80.
Note that we can add any constant to all of the elements of \vec y without violating any of the constraints - this represents adjusting the base price of the product. This is because in the reduced cost formula, the constant added to y_u and y_v will cancel each other out.
What do the reduced costs \overline w_{uv} = w_{uv} + y_u - y_v for arcs mean? Well, we might think of y_v as the buying/selling price at node v, so the \overline w_{ab} could be thought of as the cost of buying a unit of a good at u, transporting it to v, and then selling it at v.
If the reduced cost of an arc is negative, we would make a profit by transporting goods along the arc - we want to include that arc in our spanning tree. If the reduced costs of a node is 0, then the prices are fair, so we are ambivalent about including the arc in the tree. If the reduced cost is positive, we would lose money by transporting the goods, so we want to exclude the arc from our spanning tree.
Note that when we're going network simplex, the dual will be infeasible until the very end, because we allow the reduced costs to be negative and keep changing things until they're not.
In the normal simplex algorithm, we discover that the LP is unbounded when we pick an entering variable, but we can't find a leaving variable - the variables' columns in the tableau are all non-positive, which means we can add it as many times as we want, without making the constraints infeasible.
Analogously, a transshipment problem is unbounded when we cannot pick a leaving arc - if and only if we create a cycle by adding our entering arc such that all the arcs in the cycle are forward arcs (a negative cycle). This causes all of the reduced costs to be negative. Given a cycle v_0, \ldots, v_n, y_{v_k} = y_{v_0} + w_{v_0 v_1} + \ldots w_{v_{k - 1} v_k}, and the reduced cost of any arc v_k v_{k + 1} is then \overline w_{uv} = w_{v_0 v_1} + \ldots + w_{v_{k - 1} v_k}. Since v_k v_{k + 1} is entering, \overline w_{v_k v_{k + 1}} must be negative, so the cycle is a negative dicycle.
Intuitively, we can think of this as being a case where we could just keep shipping goods around and around the cycle to make more and more profit, with no uppoer bound on the amount of profit. In other words, we can send an arbitrarily large flow along this negative dicycle at an arbitrarily low overall cost, which makes it unbounded.
As we looked at earlier, a feasible transshipment problem is unbounded if and only if there is a negative dicycle. Proof:
Let x^* be a feasible solution for the transshipment problem (this must exist since the problem is known to be feasible).
See assignment 3 for the forward direction. We will only prove the reverse direction here.
Assume there is a negative dicycle C. Let x_{ij}^c = \begin{cases} 1 &\text{if } ij \in C \\ 0 &\text{otherwise} \end{cases}.
Clearly, x^c(\delta(\overline v)) = x^c(\delta(v)), since C is a directed cycle.
So x^* + tx^c is also a feasible solution for any t \ge 0. Verify feasibility for main constraints: for each v, (x^* + x^c)(\delta(\overline v)) - (x^* + x^c)(\delta(v)) = x^*(\delta(\overline v)) - x^c(\delta(v)) + t(v^c(\delta(\overline v)) - x^c(\delta(v))) = b_v + t \times 0 = b_b.
Since x^* \ge \vec 0, t \ge 0, and x^c \ge \vec 0, thenon-negativity constraints x^* + t x^c \ge 0 are satisfied.
Clearly, \vec w \cdot x^* + t w(C), the objective function value, goes to infinity as t goes to infinity since w(C) < 0, so the LP is unbounded.
Suppose we have a set of nodes S \subseteq N, and \vec xx is a solution that satisfies the flow constraints. Then \vec b(S) = \vec x(\delta(\overline S)) - \vec x(\delta(S)). In other words, when we have a bunch of nodes, the net inflow to all of those is the sum of all the net inflows for those nodes. Proof:
Since \vec x satisfies the flow constraints, \vec x(\delta(\overline v)) - \vec x(\delta(v)) for all v \in N. Then \vec b(S) = \sum_{v \in S} \vec x(\delta(\overline v)) - \sum_{v \in S} \vec x(\delta(v)).
If an arc ij has i \in S, j \in S, then it contributes x_{ij} to both i and j, so they cancel out. If i \in S, j \notin S, ij contributes x_{ij} to \sum_{v \in S} \vec x(\delta(v)). If i \notin S, j \in S, ij contributes x_{ij} to \sum_{v \in S} \vec x(\delta(\overline v)).
So \sum_{v \in S} \vec x(\delta(\overline v)) - \sum_{v \in S} \vec x(\delta(v)) = \vec x(\delta(\overline S)) - \vec x(\delta(S)) = \vec b(S), as required.
When we remove a leaving arc, we're left with two trees. We then choose an entering arc to fix the tree by connecting a node from one tree to a node of the other, in the reverse direction of the removed arc. An infeasible network occurs when the net inflow to a subset of nodes is positive, but no arc goes into it.
In other words, a TP is infeasible if and only if there exists S \subseteq N such that \vec b(S) < 0 and \delta(S) = \emptyset. Proof:
Assume there exists S \subseteq N such that \vec b(S) < 0 and \delta(S) = \emptyset. Suppose there exists a feasible solution \vec x.
From last class, we know that \vec b(S) = \vec x(\delta(\overline S)) - \vec x(\delta(S)) (the net quantity demanded in a set of nodes is the sum of all the net quantity demanded in the nodes).
Clearly, \vec x(\delta(S)) = 0 since \delta(S) = \emptyset. Clearly, \vec x(\delta(\overline S)) \ge 0 since it consists entirely of incoming arcs, which means \vec b(S) \ge 0, a contradiction.
So there cannot exist a feasible solution \vec x. S acts as a certificiate that the TP is infeasible.
For linear programs, we can use an auxilary LP to find a feasible solution. Consider an LP in SEF "max \vec c \cdot \vec x subject to A \vec x = \vec b and \vec x \ge 0". We invert constraints whose right hand side is negative, change the equalities to inequalities, add slack variables accordingly, and then try to minimize the slack variables, to get "min \vec 1 \cdot \vec s subject to A \vec x + \vec s = \vec b and \vec x \ge 0 and \vec s \ge 0". The original LP must then be feasible if and only if this auxilary LP's objective function value ends up being 0.
We can apply this to TPs as well, using a very similar technique. Suppose we have a TP "max \vec c \cdot \vec x subject to M \vec x = \vec b and \vec x \ge 0". For each constraint i, we add a slack variable s_i if b_i > 0, and subtract a slack variable s_i if b_i < 0 (no slack variable if b_i = 0). We then add a redundant constraint \sum_{i: b_i < 0} s_i - \sum_{i: b_i \ge 0} = 0. The new TP then tries to minimize the sum of all the slack variables.
Intuitively, we added a node with net quantity demanded 0 (the redundant constraint) that connects to nodes with positive quantity demanded, and connects from nodes with negative quantity supplied, all with weight 1. We're easily able to find a feasible basis because we can send all our supply to that redundant node, and distribute it from there to all the places it's demanded, and once we have a feasible basis, we can optimize to avoid those arcs connecting to the redundant node using TP Simplex.
Exam questions will be similar to assignment questions.
So given a TP with network D and demands b, we get the auxilary TP by adding a new node v with demand 0, arcs pv for all p \in N such that b_p < 0, arcs vp for all p \in N such that b_p > 0, to get the new network D'. Let arcs have cost 0 in D' they're from D, and 1 when they're from arcs we just added. Then D has a feasible solution if and only if the auxilary TP D' has an optimal solution with objective function value 0. Proof:
Assume there is a feasible flow for D. Then, if we copy the flow into D' and set the rest of the flow values to 0, we get a feasible solution for D', and it has objective value 0 since it doesn't use any of the new arcs - this is an optimal solution with objective function value 0.
Assume there's an optimal solution with objective function value 0 in D'. Then there is a feasible flow for D' such that all arcs that we added with cost 1 have no flow through them. The flow on the remaining arcs (the arcs that are also in D) must then form a feasible flow for D.
Additionally, we can ensure this is a feasible tree flow because the TP Simplex method always finds an optimal spanning tree.
Now for the other direction. Assume D is infeasible. Then D' must have an optimal tree flow T that contains the artificial node v we added.
Consider this tree flow with that new node v as the root, particularly the artificial arcs (arcs we added to connect v with other nodes).
Let N^- be the set of nodes that are adjacent to v within T having negative net quantity demanded, and N^+ be those with positive net quantity demanded.
Clearly, each node u in N^- or N^+ is the root of its own subtree in T. Let T_u be that subtree.
Let y be a feasible potential where y_v = 0. Each node u \in N^- is incident with an arc uv with cost 1, so y_u = -1. Likewise for each u \in N^+, so y_u = 1.
Since all arcs in D' that are also in D have cost 0, any node T_u where u \in N^-has potential -1, and any node T_u where u \in N^+ has potential 1.
Let S = \set{w \in T_u : u \in N^-} - all nodes from all subtrees rooted in N^-.
Clearly, all arcs from S to v have positive positive flow, so \vec x(\delta(S)) > 0 and x(\delta(\overline S)) = 0 (there's no arcs \overline S in T since it's a tree).
By the previous lemma, \vec b(S) < 0. If there exists an arc pq \in \delta(S) in D where p \in S, q \notin S, then y_p = -1, w_{pq} = 0, y_q = 1, so \overline w_{pq} = -1.
So y is not a feasible potential, a contradiction, so \delta(S) = \emptyset, as required. ;wip: where's the contradiction
This is a generalization of the transshipment problem, where arcs have a maximum capacity - the flow on a given arc might be limited by the arc's capacity.
When we draw the networks, we now label nodes with net quantity demanded, and arcs with pairs containing arc costs and arc capacity.
We can still formulate this as an LP: given a digraph D = \tup{N, A}, node demands \vec b \in \mb{R}^N, arc costs w \in \mb{R}^A, arc capacities c \in \mb{R}^A, we have the LP "minimize \vec w \cdot \vec x subject to \vec x(\delta(\overline v)) - \vec x(\delta(v)) = b_v for all v \in N and x_{uv} \le c_{uv} for all uv \in A and \vec x \ge \vec 0".
We usually write this as "minimize \vec w \cdot \vec x subject to \vec x(\delta(\overline v)) - \vec x(\delta(v)) = b_v for all v \in N and x_{uv} + s_{uv} \le c_{uv} for all uv \in A and \vec x \ge \vec 0 and \vec s \ge \vec 0", where s_{uv} are slack variables.
Consider now the dual of this LP. For the "x_{uv} \le c_{uv} for all uv \in A" constraint, we have to multiply by -1 to get "-x_{uv} \ge -c_{uv} for all uv \in A". We'll represent the dual variables as two vectors now, \vec y for the flow constraints, and \vec z for the capacity constraints. We now have the dual "maximize \vec b \cdot \vec y - \vec c \cdot \vec z subject to -y_u + y_v - z \le w_{uv} for all uv \in A and \vec y, \vec z \ge 0".
For TP instances, basic solutions were spanning trees. What does a basic solution look like for the MCFP?
There are 2m variables - two for each arc. The rank of the matrix is m + n - 1, since the incidence matrix has rank n - 1 and the m capacity constraints are linearly independent. Therefore, a basic solution must have m + n - 1 basic variables, and all other variables must be 0.
For each uv \in A, at least one of x_{uv} or s_{uv} is basic - if they weren't, then x_{uv} + s_{uv} = 0 \ne c_{uv}, which is a contradiction. If x_{uv} is basic but s_{uv} is not, then x_{uv} = c_{uv}. If s_{uv} is basic but x_{uv} is not, then x_{uv} = 0. Otherwise, 0 \le x_{uv} \le c_{uv}.
Let k be the number of arcs uv in the basic solution such that both x_{uv} and s_{uv} are basic solutions. Then there must be m - k arcs that appear exactly once in a basic solution, while k arcs appear twice each. So m + n - 1 = 2k + (m - k), so k = n - 1.
If we have a set of arcs containing a cycle and both variables for arcs in that set are basic, then the columns of the s_{uv} values cancel out x_{uv} in the bottom rows in the LP's matrix form (for the capacity constraints). The remaining, uncancelled-out values of x_{uv} form the incidence matrix for the graph, which is linearly dependent. The set of arcs where both variables are basic for each arc in the set form a spanning tree. All non-tree arcs must then have flow at 0 or at capacity.
Consider now the dual of the MCFP: "maximize \vec b \cdot \vec y - \vec c \cdot \vec z subject to -y_u + y_v - z_{uv} \le w_{uv} and \vec z \ge \vec 0".
Complementary slackness conditions:
Each z_{uv} is only present in two constraints: z_{uv} \ge 0 and -y_u + y_v - z_{uv} \le w_{uv} is true. Since the reduced cost is defined as \overline w_{uv} = y_u + w_{uv} - y_v, we have \overline w_{uv} \ge -z_{uv} or z_{uv} \ge -\overline w_{uv}.
In the objective function, we maximize -c_{uv} z_{uv}, which means we want to minimize z_{uv} - z_{uv} = \max\set{0, -\overline w_{uv}}.
Clearly, the first complementary slackness condition is equivalent to: If z_{uv} > 0, then x_{uv} = c_{uv}. z_{uv} > 0 if and only if \overline w_{uv} < 0.
Clearly, the second complementary slackness condition is equivalent to: If \overline w_{uv} < 0, then x_{uv} = c_{uv}.
;wip: missed due to interviews
;wip: missed due to interviews
;wip: missed due to interviews
;wip: missed due to interviews
;wip: missed due to interviews
;wip: dijkstra's algo
Dijkstra's algorithm requires that all arc costs be non-negative. Specifically, this is required to enforce to invariant that adding a node will strictly increase the cost.
Midterm will cover everything up to assignment 5.
Dijkstra's algorithm for the shortest s, t-dipaths solves the problems for a given s and any t \in N - it gets the shortest path from one vertex to every other vertex. In other words, Dijkstra's algorithm produces a tree where s is the root, and every path starting from s is the shortest possible path.
A tree T is a rooted tree at s if the unique s, t-path in T is a directed s, t-path for all nodes t \in T. Dijkstra's algorithm starting at s always finds a tree rooted at s.
If v_0, \ldots, v_k is the shortest v_0, v_k-dipath, then v_0, \ldots, v_i is the shortest v_0, v_i-dipath for any 0 \le i \le k. In other words, any prefix of a shortest path between two vertices is itself also a shortest path (assuming no negative cycles). Proof:
Suppose P = v_0, \ldots, v_i is not the shortest v_0, \ldots, v_i is not the shortest v_0, v_i-path for some i. Let i be the largest possible such that P doesn't intersect v_i, \ldots, v_k.
Then there exists another v_0, v_i-path P' with lower cost.
If P' doesn't include any of v_{i + 1}, \ldots, v_k, then P', v_{i + 1}, \ldots, v_k is a v_0, v_k-path with smaller cost - a contradiction.
This algorithm works even if there are negative costs, though we still can't have negative cycles (the algorithm will detect those, however).
Essentially, we start with an infeasible potential, and then repeatedly check for arcs that violate feasibility (arcs u, v such that \overline w_{uv} < 0) and fix that by changing some potentials.
Bellman-Ford algorithm:
This work by Anthony Zhang is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright 2013-2017 Anthony Zhang.