\section{Basic Network Models}\label{S:Basic_Network_Models}
\setcounter{progress_ck_counter}{0}

\noi Transportation and transshipment problems are special cases of the
\emph{minimum cost network flow problem}, which we now describe in its general form.

\subsection{The Minimum Cost Network Flow
Problem Formulation}\label{SS:Minimum_Cost_Flow_Formulation}

\noi
The minimum cost network flow problem\index{minimum cost network flow problem} arises from a collection of $n$ \emph{nodes}\index{nodes} each pair of which is connected by a \emph{directed arc}\index{directed arc}. To the arc starting at node $i$ and ending at node  $j$, where $1 \leq i,j \leq n$ we may associate two quantities, an arc \emph{flow capacity}\index{flow capacity}, $M_{ij}$, and a \emph{cost per unit flow} along the arc, $C_{ij}$. Each node $i$ is
assigned a real number, $f_i$ which measures the \emph{net outflow} at that node. If $f_i >0$, we view
node $i$ as a \emph{source}\index{source}, if $f_i<0$ it is a \emph{sink}\index{sink}, and if $f_i=0$, it is a \emph{transshipment point}.

\newpar
From a physical perspective, we may view the network as modeling the flow of fluid through pipes. Sources and sinks are locations from which fluid enters and exits the system, with rate of fluid entry or exit at node $i$ measured by $f_i$. Arcs represent pipes, with $M_{ij}$ denoting the maximum possible fluid flow through the pipe starting at node $i$
and ending at node$j$. Figure \ref{Fi:Basic_Network_Models_Minimum_Cost_Flow_Nodes} illustrates flow between two nodes. Note that there exist two flow capacities between these two nodes, $M_{ij}$ and $M_{ji}$, and that these values need not be equal. For example, if $M_{ij}>0$ and $M_{ji}=0$, then flow is permitted only in the direction from node $i$ and to $j$ but not in the reverse direction.

\begin{figure}[h]
\centering
\psfrag{ni}[Bc][Bc]{$f_i$}
\psfrag{nj}[Bc][Bc]{$f_j$}
\psfrag{fij}[Bc][Bc]{$M_{ij}$}
\psfrag{fji}[Bc][Bc]{$M_{ji}$}
\includegraphics{images/f04x03x01.eps}
\caption{Two nodes in the minimum cost flow problem.}
\label{Fi:Basic_Network_Models_Minimum_Cost_Flow_Nodes}
\end{figure}

\newpar
The minimum cost network flow problem is the LP that seeks to determine the flow values between nodes that minimize the total cost of fluid flow through the network, subject to the flow constraints and the assumption that conservation of flow occurs at each node. By conservation of flow\index{conservation of flow|see{minimum cost network flow problem!conservation of flow}} we mean the combined net outflow at node $i$ due to fluid both flowing in from and also flowing out to adjacent nodes is given by $f_i$. If $x_{ij}$, where
$1 \leq i,j \leq n$, is the decision variable representing the flow from node $i$ to node $j$,
the minimum cost network flow LP is given by (\ref{E:ShortestPath_MaximumFlow_MinimumCostLP}):

\begin{align}\label{E:ShortestPath_MaximumFlow_MinimumCostLP}
 \mbox{minimize } z &=\sum_{i=1}^n \sum_{j=1}^n C_{ij}x_{ij}   \\
	\mbox{ subject to} \notag\\
\sum_{j=1}^n x_{ij} - \sum_{j=1}^n x_{ji} &= f_i, \mbox{ for } 1 \leq i \leq n \notag \\
x_{ij} \leq M_{ij} &\mbox{ for } 1 \leq i,j \leq n \notag \\
x_{ij} \geq 0 &\mbox{ for } 1 \leq i,j \leq n. \notag
\end{align}

\newpar
Note that the conservation constraints, when summed over $i$, lead to
\begin{align*}
\sum_{i=1}^n f_i &= \sum_{i=1}^n \left( \sum_{j=1}^n x_{ij} - \sum_{j=1}^n x_{ji} \right) \\
&= \sum_{i=1}^n \sum_{j=1}^n x_{ij} - \sum_{i=1}^n \sum_{j=1}^n x_{ji} \\
% &= \sum_{i=1}^n \sum_{j=1}^n x_{ij} - \sum_{j=1}^n \sum_{i=1}^n x_{ji} \\
% &= \sum_{i=1}^n \sum_{j=1}^n x_{ij} - \sum_{i=1}^n \sum_{j=1}^n x_{ij} \\
&= 0.
\end{align*}

\noi Hence, a necessary condition for (\ref{E:ShortestPath_MaximumFlow_MinimumCostLP})
to be feasible is that $\ds \sum_{i=1}^n f_i=0$.

\newpar
Both the transportation\index{transportation problem!as a minimum cost network flow problem} and transshipment problems from Section \ref{S:Transportation_Transshipment}
are examples of minimum cost network flow LPs. For the first type of problem, there exist two classes of nodes, those at which the net outflow is positive, the supply points, and those at which it is negative, the demand points. The net outflow numbers represent the respective supply and demand amounts. The available supply from the first type of point may be used as the flow capacity to any demand point. The flow capacity along any arc starting and ending at two supply points as well as along any arc starting at a demand point is zero. For the transhipment LP, there exists a third class of nodes, namely those at which the net outflow is zero.

\newpar
We already know from Theorem \ref{Th:Transportation_Transshipment_IntegralSolutions} that
the solution of the balanced transportation problem having integer supply and demand amounts is
itself integer-valued. Under appropriate conditions, this result generalizes
to the minimum network flow problem problem and is spelled out by Theorem \ref{Th:ShortestPath_MaximumFlow_Integrality}, sometimes known as the \emph{Integrality
Theorem}.\index{minimum cost network flow problem!Integrality Theorem}

\begin{theorem}\label{Th:ShortestPath_MaximumFlow_Integrality}
Assume in LP (\ref{E:ShortestPath_MaximumFlow_MinimumCostLP}) that
the flow constraints, $M_{ij}$, where $1 \leq i,j \leq n$, and net outflows $f_i$,
where $1 \leq i \leq n$ are integer-valued. Then the decision variable values in any basic feasible
solution are also integer-valued.
\end{theorem}

\subsection{Formulating and Solving the Minimum Cost Network Flow Problem with Maple}\index{minimum cost network flow problem!formulating and solving with Maple}

\noi Maple list, array, and matrix structures provide a straightforward means for solving minimum network flow problems. For example, consider the network of 5 nodes depicted in Figure \ref{Fi:Shortest_Path_MaximumFlow_MultipleNodes}. Nodes are labeled I-V, together with their
corresponding outflows. Along each arc is an ordered pair, whose entries represent
cost and flow capacity, respectively, along the arc.

\begin{figure}[h]
\centering
\includegraphics{images/f04x03x02.eps}
\caption{Five-node network with corresponding outflow numbers, costs, and flow capacities.}
\label{Fi:Shortest_Path_MaximumFlow_MultipleNodes}
\end{figure}

\newpar
The following worksheet constructs the solution to the corresponding minimum network flow problem. Output has been suppressed with the exception of the final solution.

\begin{maplelist}
\item \mf{with(LinearAlgebra):with(Optimization):}
\item \mf{f:=[3,-1,-2,-4,4]: \newline \# Outflow numbers corresponding to nodes.}
\item \mf{M:=Matrix(5,5,
\newline [0,4,0,0,4,0,0,3,3,0,0,0,0,3,0,0,0,0,0,0,0,4,0,0,0]): \newline \# Matrix of flow capacities.}
\item \mf{C:=Matrix(5,5,
\newline [0,3,0,0,6,0,0,3,3,0,0,0,0,2,0,0,0,0,0,0,0,4,0,0,0]): \newline \# Matrix
of unit flow costs.}
\item \mf{x:=array(1..5,1..5): \newline \# Array of decision variables.}
\item \mf{z:=add(add(C[i,j]*x[i,j],j=1..5),i=1..5): \newline \# Network cost function.}
\item \mf{FlowConservation:= \newline seq(add(x[i,j],j=1..5)-add(x[j,i],j=1..5)=f[i],i=1..5):
\newline \# Conservation of flow constraints.}
\item \mf{FlowCapacities:=seq(seq(x[i,j]<=M[i,j],j=1..5),i=1..5):
\newline \# Flow capacity constraints.}
\item \mf{LPSolve(z,[FlowConservation,FlowCapacities],
\newline assume=nonnegative):
\newline \# Solve minimum cost flow LP, suppressing output.}
\item \mf{assign(\%[2]): \newline \# Assign the decision variables to their solution values.}
\item \mf{print(x,z); \newline \# Print the solution array along with objective value.}
\mo{x:=\begin{bmatrix} 0 & 3 & 0 & 0 & 0 \\
0 & 0 & 3 & 3 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 4 & 0 & 0 & 0 \\
\end{bmatrix},45
}
\end{maplelist}


\subsection{The Shortest Path Problem}\label{SS:Shortest_Path}\index{shortest path problem}

\noi One of the simplest examples of a minimum cost network flow problem arises
 when we seek the shortest path of travel starting at one location and ending at another, given various routes from which to choose. The starting point may be viewed as a source with net outflow 1, the destination as a sink with outflow -1, and intermediate locations as transshipment points. If distances between locations are viewed as transportation costs, the shortest path problem reduces to that of a transshipment problem whose objective is to minimize the cost of transporting one unit from the source to the sink.

\newpar
For example, suppose an individual wishes to travel from his home in Grand Rapids, Michigan to Graceland, Tennessee and is considering routes that pass through the cities of Chicago, Indianapolis, Lansing, and St. Louis. Approximate distances between the various pairs of cities are shown in Figure \ref{Fi:Basic_Network_Models_Driving_Distances}. Assume that the lack of a single segment connecting two cities, e.g., Grand Rapids and St. Louis, indicates that a direct route between those two cities is not under consideration. That arrows in the diagram are bidirectional indicates that travel is possible in either direction and that the corresponding transportation costs, i.e., distances, are equal.

\begin{figure}[h]
\centering
\includegraphics[width=.7\linewidth]{images/f04x03x03.eps}
\caption{Driving distances between various cities.}
\label{Fi:Basic_Network_Models_Driving_Distances}
\end{figure}

\newpar
Our goal is to determine the path of shortest length that starts at Grand Rapids and ends at Graceland, traveling only upon segments shown in Figure \ref{Fi:Basic_Network_Models_Driving_Distances}.

\newpar
We begin by numbering the cities as shown in the figure and by letting $x_{ij}$, where
$1 \leq i,j \leq 6$, denote the fraction of the one unit that
is transported from city $i$ to city $j$. Because city 1 is a source, city 6 is a sink,
and all other cities are transshipment points, we have $f_1=1$, $f_6=-1$, and $f_2=f_3=f_4=f_5=0$.
For pairs of cities connected by arcs, we set the flow capacity equal to 1. For pairs not connected, we set the capacity to 0. Thus, since all net outflows and all flow capacities are integer-valued, we conclude by
Theorem \ref{Th:ShortestPath_MaximumFlow_Integrality} that
the LP's solution will yield integer-valued decision variable values. In particular, if
travel is not possible between cities $i$ and $j$, we know a priori that $x_{ij}=x_{ji}=0$.

\newpar
Costs associated with the objective function are determined using inter-city driving distances, which we record by the matrix

\begin{equation}\label{E:ShortestPath_MaximumFlow_DistanceMatrix}
C=\begin{bmatrix} 0 & 140 & 220 & 70 & 0 & 0 \\
140 & 0 & 180 & 0 & 300 & 0 \\
220 & 180 & 0 & 250 & 0 & 460 \\
70 & 0 & 250 & 0 & 0 & 720 \\
0 & 300 & 0 & 0 & 0 & 250 \\
0 & 0 & 460 & 720 & 250 & 0
\end{bmatrix}.
\end{equation}

\noi
Note that our flow capacity constraints already guarantee that the
decision variable corresponding to pairs of cities between which travel
is not possible must equal 0 in the solution. Thus, in our cost matrix, we may set to zero (or any value, for that matter) the cost corresponding to any such pair of cities. Observe also that
the matrix $C$ is symmetric, i.e., $C=C^t$, which reflects the facts flow is bidirectional and that transportation costs between any two nodes are the same, regardless of direction.

\newpar
Using $C$ we then have the objective function
\begin{equation}\label{E:ShortestPath_MaximumFlow_DistanceObjective}
z=\mbox{Total Distance Travelled}= \sum_{i=1}^6 \sum_{j=1}^6 C_{ij}x_{ij}.
\end{equation}

\noi
Using the objective $z$, along with the flow capacities, and conservation of flow constraints we have the information required to solve the minimum cost flow problem. Its solution, as computed using
Maple, is given by $z=680$, $x_{13}=x_{36}=1$ and all other decision variables equal to zero. Thus, the shortest path corresponds to the 680-mile route from Grand Rapids to Indianapolis to Graceland.

\newpar
Clearly, many variants of this problem exist. For example, the objective can become one of minimizing
the time, not the distance, required to travel from the source to the sink.

\begin{progress_ck}\label{Th:DrivingProgressCheck}\label{Th:DrivingProgressCheck}
Suppose that driving speeds between all pairs of cities in Figure \ref{Fi:Basic_Network_Models_Driving_Distances} is 70 miles per hour, with the exception
of the segment from Grand Rapids to Indianapolis, where speed is limited to 55 miles per hour.
Assuming that one travels from one city to another at a constant speed equal to the legal maximum,
determine the route that minimizes the time required to travel from Grand Rapids to Graceland.
\end{progress_ck}

\subsection{Maximum Flow Problems}\label{SS:Maximum_Flow}\index{maximum flow problem}

\noi The maximum flow problem is another example of a minimum cost network flow problem, which, like the shortest path problem, involves a single source, a single sink, and transshipment points.

\newpar
For example, a municipality wishes to design
 a plan that maximizes the flow of wastewater to a local sewage treatment plant. Figure \ref{Fi:Basic_Network_Models_Maximum_Flow}
depicts a community (labeled I), which sends its wastewater to three different pumping stations (labeled II, III, and IV), which, in turn, transport the wastewater to a sewage treatment facility (labeled V).
Directions of possible flow along pipelines are depicted by arrows, with the flow capacity of each pipe,
as measured in units of volume per unit time, denoted by the number adjacent to the corresponding arrow. The city seeks to determine what flow through the given pipes will maximize total possible flow from the city and to the treatment plant, subject to the prescribed flow capacities.

\begin{figure}[h]
\centering
\includegraphics{images/f04x03x04.eps}
\hfil
\caption{Wastewater flow diagram.}
\label{Fi:Basic_Network_Models_Maximum_Flow}
\end{figure}

\newpar
We begin by numbering the city, pumping station, and treatment plant as shown in Figure \ref{Fi:Basic_Network_Models_Maximum_Flow}, and we let $x_{ij}$, where
$1 \leq i,j \leq 5$, denote the flow rate (in volume of flow per unit time) from location
$i$ to location $j$. Because we do not know the net outflow from the city (it is, after all, the quantity we seek to maximize), we must alter the problem slightly without changing the nature
of the solution. The key is to add an ``artificial'' arc\index{maximum flow problem!artificial arc} connecting the treatment plant to the city and to view both the plant and city as transshipment points. Hence, $f_1=f_2=f_3=f_4=f_5=0$. We also set the flow capacity along this new arc to a large number, $m$, such as any number greater than the sum of the already-existing capacities. We use $m=100$.

\newpar
Our goal is to maximize the flow leaving the city or, by conservation, the flow along the
 ``artificial'' arc from the plant to the city. In other words, we seek to maximize $x_{51}$, equivalently minimize $z=-x_{51}$. Hence, we set $C_{51}=-1$ and all other unit flow
costs to zero, which gives us
$\ds
C= \begin{bmatrix} 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
-1 & 0 & 0 & 0 & 0 \\
\end{bmatrix}$. Along
with
$\ds
M= \begin{bmatrix}
0 & 2 & 3 & 0 & 0 \\
0 & 0 & 3 & 4 & 0 \\
0 & 0 & 0 & 0 & 2 \\
0 & 0 & 0 & 0 & 1 \\
100 & 0 & 0 & 0 & 0 \\
\end{bmatrix}$,
we have all the data needed to solve the problem of maximizing the flow through the city.

\begin{progress_ck}
Use Maple to verify that the flow from the city is maximized when $x_{12}=x_{24}=x_{45}=1$, $x_{13}=x_{35}=2$, and $x_{51}=3$.
\end{progress_ck}


\section*{Exercises Section \protect\ref{S:Basic_Network_Models}}

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_ShortestPath_MaximumFlow}

\endinput 