In order to get a better understanding of the network simplex approach we ini-tially look at the minimum cost flow problem without capacities. This problem is also called thetransshipment problem. Given a directed graphG= (V, E) with demandsdi for each vertexi∈V and unit transportation costwefor each edgee∈E find the minimum cost flow that satisfies the demand constraints.
Assume Gis connected. Otherwise the problem simply reduces to a transship-ment problem for each of the components in G. A tree in a directed graph is a set T ⊆E, such that, T is a tree in the underlying undirected graph. A tree solution for the transshipment-problem given by G = (V, E), demands bi, i∈V and costswe, e∈E, is a flowx∈ RE satisfying:
∀i∈V : fx(i) =bi
∀e /∈T : xe= 0
So there is no flow on edges not inT, and all demands are satisfied. Note that
7.2 Network Simplex for The Transshipment problem 123
Figure 7.4: Let vertex 1 be the root vertex. Consider edgehas shown it defines two sets RTh andPhT
tree solutions are normallynotfeasible, since edges with negative flow may exist (cf. basic solutions andfeasiblebasic solutions in linear programming).
Initially we may ask whether there exists a tree solution for any tree T. The answer is yes, and can be seen by the following constructive argument. Select a vertex r and call it the root. It can be any vertex. Consider an edge h in T. The edgehpartitionsV into two sets, one containing rdenotedRTh and the remainderPhT =V \RTh (see Figure 7.4). Ifhstarts inRhT and (consequently)
So a treeT uniquely defines a tree solution. In the example in Figure 7.4xh= 8.
It is essential to note that any feasible solution can be transformed into a tree solution. Consequently this will allow us to only look at tree solutions.
Theorem 7.1 If the transshipment problem defined by G= (V, E, w, b) has a feasible solution, then it also has a feasible tree solution.
124 The Minimum Cost Flow Problem
Proof: Letxbe a feasible solution in G. Ifxis not a tree solution then there must exist a circuitCwhere all edges have a positive flow. We can assume thatC has at least one backward edge. Letα= min{xe:e∈C, eis a backward edge}.
Now replace xe by xe+αif eis a forward edge in C, and byxe−α ife is a backward edge in C. The new xis feasible, and moreover, has one circuit less that the initial flow. If the flow is a tree solution we are done, if not, we continue the procedure. Note that each time we make an “update” to the flow, at least one edge with get flow equal to 0 and that we never put flow onto an edge with a flow of 0. Therefore we must terminate after a finite number of iterations. △ If the flow xis an optimal solution and there exists a circuit C with positive flow, C must have zero cost. This means that the approach used in the proof above can be used to generate a new optimal solution in which fewer edges have a positive flow. So it can be proved that:
Theorem 7.2 If the transshipment problem defined by G= (V, E, w, b)has an optimal solution then it also has an optimal tree solution.
The results of these two theorems are quite powerful. From now on we can restrict ourselves to look only on tree solutions. Consequently, the network simplex method moves from tree solution to tree solution using negative cost circuitsCeT consisting of tree edgesand exactly onenon-tree edgee(think of the tree edges as basic variables and the non-tree edge as the non-basic variable of a simplex iteration). Remember that the non-tree edgeeuniquely defines a circuit withT. Each edgeewill define a unique circuit with the characteristics:
• CeT ⊆T ∪ {e}
• eis an forward edge inCeT This is illustrated in Figure 7.5.
Consider the vector of potentials y ∈ RV. Set the vertex potential yi, i∈ V to the cost of the (simple) path inT fromrto i(counted with sign: plus for a forward edge, minus for a backward edge). It now holds that for alli, j∈V, the cost of the path from itoj in T equalsyj−yi (why ?). But then the reduced costs ¯wij (defined bywij+yi−yj) satisfy:
∀e∈T : w¯e= 0
∀e /∈T : w¯e=w(CeT)
IfT determines afeasibletree solutionxandCeT has non-negative cost∀e /∈T
7.2 Network Simplex for The Transshipment problem 125
Figure 7.5: An example of the definition of the unique circuitCeT by the edgee.
The edge (6,5) defines the circuith3,4,6,5,3iand the anti clockwise orientation
(i.e. ¯we ≥0), then xis optimal. Now the network simplex algorithm for the transshipment problem can be stated:
Algorithm 15: The Network Simplex Algorithm for the Transshipment Problem
find a treeT with a corresponding feasible tree solutionx
1
select anr∈V as root forT
2
computeyi as the length of ther−i–path inT, costs counted with sign
3
while∃(i, j) : ¯wij =wij+yi−yj<0do
4
Select an edge with ¯wij <0
5
if all edges in CeT are forward edgesthen
6
STOP /* the problem is ‘‘unbounded’’ */
7
Remember as flow is increased in the algorithm it is done with respect to the orientation defined by the edge that defines the circuit, that is, increase flow in forward edges and decrease flow in backward edges.
Testing whetherT satisfies the optimality conditions is relatively easy. We can compute y in time O(n) and thereafter ¯w can be computed in O(m). With the simple operations involved and the modest time complexity this is certainly going to be faster than running Bellman-Fords algorithm.
An issue that we have not touched upon is how to construct the initial tree. One
126 The Minimum Cost Flow Problem
Figure 7.6: The solution of an transshipment problem using the network simplex algorithm. The labels on the edges are ue, xe. Bold edges identify the tree solution
approach is the following: We can use the tree T whose edges are (r, i) where i∈ V \ {r} and bi ≥0 and edges (i, r) where i∈V \ {r} and bi <0. Not all these edges may exist. If they do not exist we add them toGbut assign them a large enough cost to secure they will not be part of an optimal solution.
Let us demonstrate the network simplex algorithm by the example in Figure 7.6.
First, we need to find an initial feasible tree solution. Having determined the tree asT ={(2,1),(1,3),(3,6),(2,4),(4,5)} we let vertex 2 be the root vertex.
Now the feasible solution wrt. tree solution is uniquely defined, and can be computed by (7.4) and (7.5) defined earlier. So we get the tree solution in the graph in the upper right of Figure 7.6. The flow corresponds to a value of 115.